A set D of vertices in a graph G = (V,E) is a locating-dominating set (LDS) if for every two vertices u,v of V-D the sets N(u)∩ D and N(v)∩ D are non-empty and different. The locating-domination number ${\gamma }_L\left(G\right)$ is the minimum cardinality of a LDS of G, and the upper locating-domination number, ${\Gamma }_L\left(G\right)$ is the maximum cardinality of a minimal LDS of G. We present different bounds on ${\Gamma }_L\left(G\right)$ and ${\gamma }_L\left(G\right)$.

Let $ex(n,G)$ denote the maximum number of edges in a graph on $n$ vertices which does not contain $G$ as a subgraph. Let $P_i$ denote a path consisting of $i$ vertices and let $m{P}_i$ denote $m$ disjoint copies of $P_i$. In this paper we count $ex(n,3P_4)$.

Let X be a Polish space, and let C₀ and C₁ be disjoint coanalytic subsets of X. The pair (C₀,C₁) is said to be complete if for every pair (D₀,D₁) of disjoint coanalytic subsets of ${\omega }^{\omega }$ there exists a continuous function $f:{\omega }^{\omega }\to X$ such that $f^{-1}\left(C₀\right)=D₀$ and $f^{-1}\left(C₁\right)=D₁$. We give several explicit examples of complete pairs of coanalytic sets.

Let $G$ be a simple connected graph with vertex set $V\left(G\right)=\{v_1,v_2,\cdots ,v_n\}$ and edge set $E\left(G\right)$, and let $d_{v_i}$ be the degree of the vertex $v_i$. Let $D\left(G\right)$ be the distance matrix and let $T_r\left(G\right)$ be the diagonal matrix of the vertex transmissions of $G$. The generalized distance matrix of $G$ is defined as $D_{\alpha }\left(G\right)=\alpha T_r\left(G\right)+(1-\alpha )D\left(G\right)$, where $0\le \alpha \le 1$. Let ${\lambda }_1\left(D_{\alpha }\left(G\right)\right)\ge {\lambda }_2\left(D_{\alpha }\left(G\right)\right)\ge ...\ge {\lambda }_n\left(D_{\alpha }\left(G\right)\right)$ be the generalized distance eigenvalues of $G$, and let $k$ be an integer with $1\le k\le n$. We denote by $S_k\left(D_{\alpha }\left(G\right)\right)={\lambda }_1\left(D_{\alpha }\left(G\right)\right)+{\lambda }_2\left(D_{\alpha }\left(G\right)\right)+...+{\lambda }_k\left(D_{\alpha }\left(G\right)\right)$ the sum of the $k$ largest generalized distance eigenvalues. The generalized distance spread of a graph $G$ is defined as $D_{\alpha }S\left(G\right)={\lambda }_1\left(D_{\alpha }\left(G\right)\right)-{\lambda }_n\left(D_{\alpha }\left(G\right)\right)$....

We determine upper bounds for $\gamma \left(Q{n}^t\right)$ and $i\left(Q{ₙ}^t\right)$, the domination and independent domination numbers, respectively, of the graph $Q{ₙ}^t$ obtained from the moves of queens on the n×n chessboard drawn on the torus.

A graph $X$, with a group $G$ of automorphisms of $X$, is said to be $(G,s)$-transitive, for some $s\ge 1$, if $G$ is transitive on $s$-arcs but not on $(s+1)$-arcs. Let $X$ be a connected $(G,s)$-transitive graph of prime valency $p\ge 5$, and $G_v$ the vertex stabilizer of a vertex $v\in V\left(X\right)$. Suppose that $G_v$ is solvable. Weiss (1974) proved that $|G_v{|\mid p(p-1)}^2$. In this paper, we prove that $G_v\cong ({\mathbb{Z}}_p⋊{\mathbb{Z}}_m)\times {\mathbb{Z}}_n$ for some positive integers $m$ and $n$ such that $ndivm$ and $m\mid p-1$.

Let ${\mu }_{n-1}\left(G\right)$ be the algebraic connectivity, and let ${\mu }_1\left(G\right)$ be the Laplacian spectral radius of a $k$-connected graph $G$ with $n$ vertices and $m$ edges. In this paper, we prove that $${\mu }_{n-1}\left(G\right)\ge \frac{2n{k}^2}{(n(n-1)-2m)(n+k-2)+2k^2},$$ with equality if and only if $G$ is the complete graph $K_n$ or $K_n-e$. Moreover, if $G$ is non-regular, then $${\mu }_1\left(G\right)<2\Delta -\frac{2(n\Delta -2m)k^2}{2(n\Delta -2m)(n^2-2n+2k)+n{k}^2},$$ where $\Delta$ stands for the maximum degree of $G$. Remark that in some cases, these two inequalities improve some previously known results.

Let $R$ be a commutative ring with nonzero identity and $J\left(R\right)$ the Jacobson radical of $R$. The Jacobson graph of $R$, denoted by ${𝔍}_R$, is defined as the graph with vertex set $R\setminus J\left(R\right)$ such that two distinct vertices $x$ and $y$ are adjacent if and only if $1-xy$ is not a unit of $R$. The genus of a simple graph $G$ is the smallest nonnegative integer $n$ such that $G$ can be embedded into an orientable surface $S_n$. In this paper, we investigate the genus number of the compact Riemann surface in which ${𝔍}_R$ can be embedded and...

Let $G_1$ and $G_2$ be two given graphs. The Ramsey number $R(G_1,G_2)$ is the least integer $r$ such that for every graph $G$ on $r$ vertices, either $G$ contains a $G_1$ or $\overline{G}$ contains a $G_2$. Parsons gave a recursive formula to determine the values of $R(P_n,K_{1,m})$, where $P_n$ is a path on $n$ vertices and $K_{1,m}$ is a star on $m+1$ vertices. In this note, we study the Ramsey numbers $R(P_n,K_1\vee F_m)$, where $F_m$ is a linear forest on $m$ vertices. We determine the exact values of $R(P_n,K_1\vee F_m)$ for the cases $m\le n$ and $m\ge 2n$, and for the case that $F_m$ has no odd component. Moreover, we...

Let $T_1,\cdots ,T_d$ be homogeneous trees with degrees $q_1+1,\cdots ,q_d+1\ge 3$, respectively. For each tree, let $𝔥:T_j\to \mathbb{Z}$ be the Busemann function with respect to a fixed boundary point (end). Its level sets are the horocycles. The horocyclic product of $T_1,\cdots ,T_d$ is the graph $\mathrm{𝖣𝖫}(q_1,\cdots ,q_d)$ consisting of all $d$-tuples $x_1\cdots x_d\in T_1\times \cdots \times T_d$ with $𝔥\left(x_1\right)+\cdots +𝔥\left(x_d\right)=0$, equipped with a natural neighbourhood relation. In the present paper, we explore the geometric, algebraic, analytic and probabilistic properties of these graphs and their isometry groups. If $d=2$ and $q_1=q_2=q$ then we obtain a Cayley graph...

Let $G$ be a finite group. The intersection graph ${\Delta }_G$ of $G$ is an undirected graph without loops and multiple edges defined as follows: the vertex set is the set of all proper nontrivial subgroups of $G$, and two distinct vertices $X$ and $Y$ are adjacent if $X\cap Y\ne 1$, where $1$ denotes the trivial subgroup of order $1$. A question was posed by Shen (2010) whether the diameters of intersection graphs of finite non-abelian simple groups have an upper bound. We answer the question and show that the diameters...

In this paper, we study the size of the giant component $C_G$ in the random geometric graph $G=G(n,r_n,f)$ of $n$ nodes independently distributed each according to a certain density $f(·)$ in ${[0,1]}^2$ satisfying ${inf}_{x\in {[0,1]}^2}f\left(x\right)gt;$ $0$. If $\frac{c_1}{n}\le r_n^2\le c_2\frac{logn}{n}$ for some positive constants $c_1$, $c_2$ and $n{r}_n^2⟶\infty$ as $n\to \infty$, we show that the giant component of $G$ contains at least $n-\mathrm{o}\left(n\right)$ nodes with probability at least $1-{\mathrm{e}}^{-\beta n{r}_n^2}$ for all $n$ and for some positive constant $\beta$. We also obtain estimates on the diameter and number of the non-giant components of $G$.

The generalized $k$-connectivity ${\kappa }_k\left(G\right)$ of a graph $G$ was introduced by Chartrand et al. in 1984. As a natural counterpart of this concept, Li et al. in 2011 introduced the concept of generalized $k$-edge-connectivity which is defined as ${\lambda }_k\left(G\right)=min\{\lambda \left(S\right):S\subseteq V\left(G\right)$ and $\left|S\right|=k\}$, where $\lambda \left(S\right)$ denotes the maximum number $\ell$ of pairwise edge-disjoint trees $T_1,T_2,...,T_{\ell }$ in $G$ such that $S\subseteq V\left(T_i\right)$ for $1\le i\le \ell$. In this paper we prove that for any two connected graphs $G$ and $H$ we have ${\lambda }_3(G\square H)\ge {\lambda }_3\left(G\right)+{\lambda }_3\left(H\right)$, where $G\square H$ is the Cartesian product of $G$ and $H$. Moreover, the bound is sharp. We also...

Let $G$ be a finite group and let $\pi \left(G\right)=\{p_1,p_2,...,p_k\}$ be the set of prime divisors of $\left|G\right|$ for which $p_1<p_2<\cdots <p_k$. The Gruenberg-Kegel graph of $G$, denoted $GK\left(G\right)$, is defined as follows: its vertex set is $\pi \left(G\right)$ and two different vertices $p_i$ and $p_j$ are adjacent by an edge if and only if $G$ contains an element of order $p_i{p}_j$. The degree of a vertex $p_i$ in $\mathrm{GK}\left(G\right)$ is denoted by $d_G\left(p_i\right)$ and the $k$-tuple $D\left(G\right)=(d_G\left(p_1\right),d_G\left(p_2\right),...,d_G\left(p_k\right))$ is said to be the degree pattern of $G$. Moreover, if $\omega \subseteq \pi \left(G\right)$ is the vertex set of a connected component of $GK\left(G\right)$, then the largest $\omega$-number which divides $\left|G\right|$, is...

Suppose that $A$ is a real symmetric matrix of order $n$. Denote by $m_A\left(0\right)$ the nullity of $A$. For a nonempty subset $\alpha$ of $\{1,2,...,n\}$, let $A\left(\alpha \right)$ be the principal submatrix of $A$ obtained from $A$ by deleting the rows and columns indexed by $\alpha$. When $m_{A\left(\alpha \right)}\left(0\right)=m_A\left(0\right)+\left|\alpha \right|$, we call $\alpha$ a P-set of $A$. It is known that every P-set of $A$ contains at most $\lfloor n/2\rfloor$ elements. The graphs of even order for which one can find a matrix attaining this bound are now completely characterized. However, the odd case turned out to be more difficult to tackle. As...