An additive hereditary graph property is any class of simple graphs, which is closed under isomorphisms unions and taking subgraphs. Let $L^a$ denote a class of all such properties. In the paper, we consider H-reducible over $L^a$ properties with H being a fixed graph. The finiteness of the sets of all minimal forbidden graphs is analyzed for such properties.

The energy of a molecular graph G is defined as the summation of the absolute values of the eigenvalues of adjacency matrix of a graph G. In this paper, an infinite class of fullerene graphs with 10n vertices, n ≥ 2, is considered. By proving centrosymmetricity of the adjacency matrix of these fullerene graphs, a lower bound for its energy is given. Our method is general and can be extended to other class of fullerene graphs.

The Chvátal-Erdös theorems imply that if G is a graph of order n ≥ 3 with κ(G) ≥ α(G), then G is hamiltonian, and if κ(G) > α(G), then G is hamiltonian-connected. We generalize these results by replacing the connectivity and independence number conditions with a weaker minimum degree and independence number condition in the presence of sufficient connectivity. More specifically, it is noted that if G is a graph of order n and k ≥ 2 is a positive integer such that κ(G) ≥ k, δ(G) > (n+k²-k)/(k+1),...

In this paper, two notions, the clique irreducibility and clique vertex irreducibility are discussed. A graph G is clique irreducible if every clique in G of size at least two, has an edge which does not lie in any other clique of G and it is clique vertex irreducible if every clique in G has a vertex which does not lie in any other clique of G. It is proved that L(G) is clique irreducible if and only if every triangle in G has a vertex of degree two. The conditions for the iterations of line graph,...

A dominating set in a graph $G$ is a connected dominating set of $G$ if it induces a connected subgraph of $G$. The minimum number of vertices in a connected dominating set of $G$ is called the connected domination number of $G$, and is denoted by ${\gamma }_c\left(G\right)$. Let $G$ be a spanning subgraph of $K_{s,s}$ and let $H$ be the complement of $G$ relative to $K_{s,s}$; that is, $K_{s,s}=G\oplus H$ is a factorization of $K_{s,s}$. The graph $G$ is $k$-${\gamma }_c$-critical relative to $K_{s,s}$ if ${\gamma }_c\left(G\right)=k$ and ${\gamma }_c(G+e)<k$ for each edge $e\in E\left(H\right)$. First, we discuss some classes of graphs whether they are ${\gamma }_c$-critical relative...

For an ordered set $W=\{w_1,w_2,\cdots ,w_k\}$ of vertices and a vertex $v$ in a connected graph $G$, the representation of $v$ with respect to $W$ is the $k$-vector $r\left(v\right|W)$ = ($d(v,w_1)$, $d(v,w_2),\cdots ,d(v,w_k))$, where $d(x,y)$ represents the distance between the vertices $x$ and $y$. The set $W$ is a resolving set for $G$ if distinct vertices of $G$ have distinct representations with respect to $W$. A resolving set for $G$ containing a minimum number of vertices is a basis for $G$. The dimension $dim\left(G\right)$ is the number of vertices in a basis for $G$. A resolving set $W$ of $G$ is connected if the subgraph...