A balanced colouring of a graph G is a colouring of some of the vertices of G with two colours, say red and blue, such that there is the same number of vertices in each colour. The balanced decomposition number f(G) of G is the minimum integer s with the following property: For any balanced colouring of G, there is a partition V (G) = V1 ∪˙ · · · ∪˙ Vr such that, for every i, Vi induces a connected subgraph of order at most s, and contains the same number of red and blue vertices. The function f(G)...

Let G be a 2-connected graph of order n satisfying α(G) = a ≤ κ(G), where α(G) and κ(G) are the independence number and the connectivity of G, respectively, and let r(m,n) denote the Ramsey number. The well-known Chvátal-Erdös Theorem states that G has a hamiltonian cycle. In this paper, we extend this theorem, and prove that G has a 2-factor with a specified number of components if n is sufficiently large. More precisely, we prove that (1) if n ≥ k·r(a+4, a+1), then G has a 2-factor with k components,...

An edge of a graph is called dot-critical if its contraction decreases the domination number. A graph is said to be dot-critical if all of its edges are dot-critical. A vertex of a graph is called critical if its deletion decreases the domination number. In A note on the domination dot-critical graphs, Discrete Appl. Math. 157 (2009) 3743-3745, Chen and Shiu constructed for each even integer k ≥ 4 infinitely many k-dot-critical graphs G with no critical vertices and k(G) = 1. In this paper, we refine...

An edge $e$ of a $k$-connected graph $G$ is said to be $k$-removable if $G-e$ is still $k$-connected. A subgraph $H$ of a $k$-connected graph is said to be $k$-contractible if its contraction results still in a $k$-connected graph. A $k$-connected graph with neither removable edge nor contractible subgraph is said to be minor minimally $k$-connected. In this paper, we show that there is a contractible subgraph in a $5$-connected graph which contains a vertex who is not contained in any triangles. Hence, every vertex of minor...

Let $G$ be a connected, undirected graph without loops and without multiple edges. For a pair of distinct vertices $u$ and $v$, a minimum $\{u,v\}$-separating set is a smallest set of edges in $G$ whose removal disconnects $u$ and $v$. The edge connectivity of $G$, denoted $\lambda \left(G\right)$, is defined to be the minimum cardinality of a minimum $\{u,v\}$-separating set as $u$ and $v$ range over all pairs of distinct vertices in $G$. We introduce and investigate the eavesdropping number, denoted $\epsilon \left(G\right)$, which is defined to be the maximum cardinality of...

The eccentric connectivity index of a graph G, ξ^C, was proposed by Sharma, Goswami and Madan. It is defined as ξ^C(G) = ∑ u ∈ V(G) degG(u)εG(u), where degG(u) denotes the degree of the vertex x in G and εG(u) = Max{d(u, x) | x ∈ V (G)}. The eccentric connectivity polynomial is a polynomial version of this topological index. In this paper, exact formulas for the eccentric connectivity polynomial of Cartesian product, symmetric difference, disjunction and join of graphs are presented.* The work...

The Gutman index and the edge-Wiener index have been extensively investigated particularly in the last decade. An important stream of re- search on graph indices is to bound indices in terms of the order and other parameters of given graph. In this paper we present asymptotically sharp upper bounds on the Gutman index and the edge-Wiener index for graphs of given order and vertex-connectivity κ, where κ is a constant. Our results substantially generalize and extend known results in the area.

A graph in a certain graph class is called minimizing if the least eigenvalue of its adjacency matrix attains the minimum among all graphs in that class. Bell et al. have identified a subclass within the connected graphs of order n and size m in which minimizing graphs belong (the complements of such graphs are either disconnected or contain a clique of size n/2 ). In this paper we discuss the minimizing graphs of a special class of graphs of order n whose complements are connected and contains...

For an ordered set $W=\{w_1,w_2,...,w_k\}$ of $k$ distinct vertices in a nontrivial connected graph $G$, the metric code of a vertex $v$ of $G$ with respect to $W$ is the $k$-vector $$\mathrm{code}\left(v\right)=(d(v,w_1),d(v,w_2),\cdots ,d(v,w_k))$$ where $d(v,w_i)$ is the distance between $v$ and $w_i$ for $1\le i\le k$. The set $W$ is a local metric set of $G$ if $\mathrm{code}\left(u\right)\ne \mathrm{code}\left(v\right)$ for every pair $u,v$ of adjacent vertices of $G$. The minimum positive integer $k$ for which $G$ has a local metric $k$-set is the local metric dimension $\mathrm{lmd}\left(G\right)$ of $G$. A local metric set of $G$ of cardinality $\mathrm{lmd}\left(G\right)$ is a local metric basis of $G$. We characterize all nontrivial connected...

Let $R$ be a commutative ring with unity and $U\left(R\right)$ be the set of unit elements of $R$. In this paper, we introduce and investigate some properties of a new kind of graph on the ring $R$, namely, the prime ideals intersection graph of $R$, denoted by $G_p\left(R\right)$. The $G_p\left(R\right)$ is a graph with vertex set $R^{*}-U\left(R\right)$ and two distinct vertices $a$ and $b$ are adjacent if and only if there exists a prime ideal $𝔭$ of $R$ such that $a,b\in 𝔭$. We obtain necessary and sufficient conditions on $R$ such that $G_p\left(R\right)$ is disconnected. We find the diameter and girth of $G_p\left(R\right)$....

The k-rainbow index rxk(G) of a connected graph G was introduced by Chartrand, Okamoto and Zhang in 2010. As a natural counterpart of the k-rainbow index, we introduce the concept of k-vertex-rainbow index rvxk(G) in this paper. In this paper, sharp upper and lower bounds of rvxk(G) are given for a connected graph G of order n, that is, 0 ≤ rvxk(G) ≤ n − 2. We obtain Nordhaus-Gaddum results for 3-vertex-rainbow index of a graph G of order n, and show that rvx3(G) + rvx3(Ḡ) = 4 for n = 4 and 2 ≤...

Let G1 = (V1, E1) and G2 = (V2, E2) be two graphs having a distinguished or root vertex, labeled 0. The hierarchical product G2 ⊓ G1 of G2 and G1 is a graph with vertex set V2 × V1. Two vertices y2y1 and x2x1 are adjacent if and only if y1x1 ∈ E1 and y2 = x2; or y2x2 ∈ E2 and y1 = x1 = 0. In this paper, the Wiener, eccentric connectivity and Zagreb indices of this new operation of graphs are computed. As an application, these topological indices for a class of alkanes are computed. ACM Computing...