Displaying similar documents to “Simple score sequences in oriented graphs.”

Notes on the independence number in the Cartesian product of graphs

G. Abay-Asmerom, R. Hammack, C.E. Larson, D.T. Taylor (2011)

Discussiones Mathematicae Graph Theory

Similarity:

Every connected graph G with radius r(G) and independence number α(G) obeys α(G) ≥ r(G). Recently the graphs for which equality holds have been classified. Here we investigate the members of this class that are Cartesian products. We show that for non-trivial graphs G and H, α(G ☐ H) = r(G ☐ H) if and only if one factor is a complete graph on two vertices, and the other is a nontrivial complete graph. We also prove a new (polynomial computable) lower bound α(G ☐ H) ≥ 2r(G)r(H)...

Clique irreducibility of some iterative classes of graphs

Aparna Lakshmanan S., A. Vijayakumar (2008)

Discussiones Mathematicae Graph Theory

Similarity:

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