Displaying similar documents to “On a Graph Transformation That Preserves the Stability Number”

On the Non-(p−1)-Partite Kp-Free Graphs

Kinnari Amin, Jill Faudree, Ronald J. Gould, Elżbieta Sidorowicz (2013)

Discussiones Mathematicae Graph Theory

Similarity:

We say that a graph G is maximal Kp-free if G does not contain Kp but if we add any new edge e ∈ E(G) to G, then the graph G + e contains Kp. We study the minimum and maximum size of non-(p − 1)-partite maximal Kp-free graphs with n vertices. We also answer the interpolation question: for which values of n and m are there any n-vertex maximal Kp-free graphs of size m?

Paired- and induced paired-domination in {E,net}-free graphs

Oliver Schaudt (2012)

Discussiones Mathematicae Graph Theory

Similarity:

A dominating set of a graph is a vertex subset that any vertex belongs to or is adjacent to. Among the many well-studied variants of domination are the so-called paired-dominating sets. A paired-dominating set is a dominating set whose induced subgraph has a perfect matching. In this paper, we continue their study. We focus on graphs that do not contain the net-graph (obtained by attaching a pendant vertex to each vertex of the triangle) or the E-graph (obtained by...

Minimal claw-free graphs

P. Dankelmann, Henda C. Swart, P. van den Berg, Wayne Goddard, M. D. Plummer (2008)

Czechoslovak Mathematical Journal

Similarity:

A graph G is a minimal claw-free graph (m.c.f. graph) if it contains no K 1 , 3 (claw) as an induced subgraph and if, for each edge e of G , G - e contains an induced claw. We investigate properties of m.c.f. graphs, establish sharp bounds on their orders and the degrees of their vertices, and characterize graphs which have m.c.f. line graphs.