Domino

Материал из WEGA
Перейти к навигации Перейти к поиску

Domino --- домино.

1. A graph which consists of two cycles of length 4 with a common edge is called a domino.

2. A domino is a graph in which every vertex is contained in at most two maximal cliques. The class of such graphs properly contains the line graphs of bipartite graphs. Every domino is a line graph of a multigraph, and hence claw-free. The class of the domino graphs is hereditary; i.e. if [math]\displaystyle{ G }[/math] is a domino, then every induced subgraph of [math]\displaystyle{ G }[/math] is also a domino.