In this paper we show bounds for the adjacent eccentric distance sum of graphs in terms of Wiener index, maximum degree and minimum degree. We extend some earlier results of Hua and Yu [Bounds for the Adjacent Eccentric Distance Sum, International Mathematical Forum, Vol. 7 (2002) no. 26, 1289–1294]. The adjacent eccentric distance sum index of the graph $G$ is defined as$${\xi }^{sv}\left(G\right)=\sum _{v\in V\left(G\right)}\frac{\epsilon \left(v\right)D\left(v\right)}{deg\left(v\right)},$$ where $\epsilon \left(v\right)$ is the eccentricity of the vertex $v$, $deg\left(v\right)$ is the degree of the vertex $v$ and$$D\left(v\right)=\sum _{u\in V\left(G\right)}d(u,v)$$ is the sum of all distances from...

For vertices x and y in a connected graph G, the detour distance D(x,y) is the length of a longest x - y path in G. An x - y path of length D(x,y) is an x - y detour. The closed detour interval ID[x,y] consists of x,y, and all vertices lying on some x -y detour of G; while for S ⊆ V(G), $I_D\left[S\right]={\bigcup }_{x,y\in S}{I}_D[x,y]$. A set S of vertices is a detour convex set if $I_D\left[S\right]=S$. The detour convex hull ${\left[S\right]}_D$ is the smallest detour convex set containing S. The detour hull number dh(G) is the minimum cardinality among subsets S of...

In a graph G, a vertex dominates itself and its neighbors. A subset S ⊆ V(G) is a double dominating set of G if S dominates every vertex of G at least twice. The minimum cardinality of a double dominating set of G is the double domination number ${\gamma }_{\times 2}\left(G\right)$. A function f(p) is defined, and it is shown that ${\gamma }_{\times 2}\left(G\right)=minf\left(p\right)$, where the minimum is taken over the n-dimensional cube $Cⁿ=p=(p₁,...,pₙ)|p_i\in IR,0\le p_i\le 1,i=1,...,n$. Using this result, it is then shown that if G has order n with minimum degree δ and average degree d, then ${\gamma }_{\times 2}\left(G\right)\le ((ln(1+d)+ln\delta +1)/\delta )n$.

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 α ∈ (0,1) and let $G=(V_G,E_G$) be a graph. According to Dunbar, Hoffman, Laskar and Markus [3] a set $D\subseteq V_G$ is called an α-dominating set of G, if $|N_G\left(u\right)\cap D|\ge \alpha d_G\left(u\right)$ for all $u\in V_G\setminus D$. We prove a series of upper bounds on the α-domination number of a graph G defined as the minimum cardinality of an α-dominating set of G.

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)$.

A maximum matching of a graph $G$ is a matching of $G$ with the largest number of edges. The matching number of a graph $G$, denoted by ${\alpha }^{\text{'}}\left(G\right)$, is the number of edges in a maximum matching of $G$. In 1966, Gallai conjectured that all the longest paths of a connected graph have a common vertex. Although this conjecture has been disproved, finding some nice classes of graphs that support this conjecture is still very meaningful and interesting. In this short note, we prove that Gallai’s conjecture...

A graph $G$ is a $\{d,d+k\}$-graph, if one vertex has degree $d+k$ and the remaining vertices of $G$ have degree $d$. In the special case of $k=0$, the graph $G$ is $d$-regular. Let $k,p\ge 0$ and $d,n\ge 1$ be integers such that $n$ and $p$ are of the same parity. If $G$ is a connected $\{d,d+k\}$-graph of order $n$ without a matching $M$ of size $2\left|M\right|=n-p$, then we show in this paper the following: If $d=2$, then $k\ge 2(p+2)$ and (i) $n\ge k+p+6$. If $d\ge 3$ is odd and $t$ an integer with $1\le t\le p+2$, then (ii) $n\ge d+k+1$ for $k\ge d(p+2)$, (iii) $n\ge d(p+3)+2t+1$ for $d(p+2-t)+t\le k\le d(p+3-t)+t-3$, (iv) $n\ge d(p+3)+2p+7$ for $k\le p$. If $d\ge 4$ is even, then (v) $n\ge d+k+2-\eta$ for $k\ge d(p+3)+p+4+\eta$, (vi) $n\ge d+k+p+2-2t=d(p+4)+p+6$ for $k=d(p+3)+4+2t$ and $p\ge 1$,...

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...

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.

An edge of $G$ is singular if it does not lie on any triangle of $G$; otherwise, it is non-singular. A vertex $u$ of a graph $G$ is called locally connected if the induced subgraph $G\left[N\right(u\left)\right]$ by its neighborhood is connected; otherwise, it is called locally disconnected. In this paper, we prove that if a connected claw-free graph $G$ of order at least three satisfies the following two conditions: (i) for each locally disconnected vertex $v$ of degree at least $3$ in $G,$ there is a nonnegative integer $s$ such...

The domination subdivision number $s{d}_{\gamma }\left(G\right)$ of a graph is the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the domination number. Arumugam showed that this number is at most three for any tree, and conjectured that the upper bound of three holds for any graph. Although we do not prove this interesting conjecture, we give an upper bound for the domination subdivision number for any graph G in terms of the minimum degrees of...