Another infinite sequence of dense triangle-free graphs.

Brandt, Stephan; Pisanski, Tomaž

Displaying similar documents to “Another infinite sequence of dense triangle-free graphs.”

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.

Neighbourhoods in line graphs

Ľubomír Šoltés (1992)

Mathematica Slovaca

Similarity:

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?