Domino

Материал из WikiGrapp
Версия от 16:56, 5 апреля 2011; Glk (обсуждение | вклад) (Новая страница: «'''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 wh…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

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.