Displaying similar documents to “A note on the critical group of a line graph.”

On the Independence Number of Edge Chromatic Critical Graphs

Shiyou Pang, Lianying Miao, Wenyao Song, Zhengke Miao (2014)

Discussiones Mathematicae Graph Theory

Similarity:

In 1968, Vizing conjectured that for any edge chromatic critical graph G = (V,E) with maximum degree △ and independence number α (G), α (G) ≤ [...] . It is known that α (G) < [...] |V |. In this paper we improve this bound when △≥ 4. Our precise result depends on the number n2 of 2-vertices in G, but in particular we prove that α (G) ≤ [...] |V | when △ ≥ 5 and n2 ≤ 2(△− 1)

The diameter of paired-domination vertex critical graphs

Michael A. Henning, Christina M. Mynhardt (2008)

Czechoslovak Mathematical Journal

Similarity:

In this paper we continue the study of paired-domination in graphs introduced by Haynes and Slater (Networks (1998), 199–206). A paired-dominating set of a graph G with no isolated vertex is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number of G , denoted by γ pr ( G ) , is the minimum cardinality of a paired-dominating set of G . The graph G is paired-domination vertex critical if for every vertex v of G that is not adjacent to a vertex of...