𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Graphs with no induced C4 and 2K2

✍ Scribed by Zoltán Blázsik; Mihály Hujter; András Pluhár; Zsolt Tuza

Book ID
103057778
Publisher
Elsevier Science
Year
1993
Tongue
English
Weight
274 KB
Volume
115
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

We characterize the structure of graphs containing neither the 4-cycle nor its complement as an induced subgraph. This self-complementary class B of graphs includes split graphs, which are graphs whose vertex set is the union of a clique and an independent set. In the members of Q, the number of cliques (as well as the number of maximal independent sets) cannot exceed the number of vertices. Moreover, these graphs are almost extremal to the theorem of .

1. Results

We study undirected graphs without loops and multiple edges. A graph G is called F-free if no induced subgraph of G is isomorphic to F. In this paper we give the structural characterization of the self-complementary class 9 of graphs which are

📜 SIMILAR VOLUMES

Constructing trees in graphs with no K2,
Constructing trees in graphs with no K2,s
✍ Suman Balasubramanian; Edward Dobson 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 150 KB

## Abstract Let __s__ ≥ 2 be an integer and __k__ > 12(__s__ − 1) an integer. We give a necessary and sufficient condition for a graph __G__ containing no __K__~2,__s__~ with $\delta(G)\ge{k}/2$ and $\Delta(G)\ge k$ to contain every tree __T__ of order __k__ + 1. We then show that every graph __G__

Total domination in 2-connected graphs a
Total domination in 2-connected graphs and in graphs with no induced 6-cycles
✍ Michael A. Henning; Anders Yeo 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 272 KB 👁 1 views

## Abstract A set __S__ of vertices in a graph __G__ is a total dominating set of __G__ if every vertex of __G__ is adjacent to some vertex in __S__. The minimum cardinality of a total dominating set of __G__ is the total domination number γ~t~(__G__) of __G__. It is known [J Graph Theory 35 (2000)