Displaying similar documents to “Recognizing maximal unfrozen graphs with respect to independent sets is CO-NP-complete.”

Extremely Irregular Graphs

M. Tavakoli, F. Rahbarnia, M. Mirzavaziri, A. R. Ashrafi, I. Gutman (2013)

Kragujevac Journal of Mathematics

Similarity:

On the total domination subdivision numbers in graphs

Seyed Sheikholeslami (2010)

Open Mathematics

Similarity:

A set S of vertices of a graph G = (V, E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γ t(G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number sdγt (G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the total domination number. Karami, Khoeilar, Sheikholeslami and Khodkar,...

Gallai and anti-Gallai graphs of a graph

Aparna Lakshmanan S., S. B. Rao, A. Vijayakumar (2007)

Mathematica Bohemica

Similarity:

The paper deals with graph operators—the Gallai graphs and the anti-Gallai graphs. We prove the existence of a finite family of forbidden subgraphs for the Gallai graphs and the anti-Gallai graphs to be H -free for any finite graph H . The case of complement reducible graphs—cographs is discussed in detail. Some relations between the chromatic number, the radius and the diameter of a graph and its Gallai and anti-Gallai graphs are also obtained.