The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

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