Split Graph
المؤلف:
Golumbic, M. C
المصدر:
Algorithmic Graph Theory and Perfect Graphs. New York: Academic Press, 1980
الجزء والصفحة:
...
19-5-2022
2043
Split Graph
A split graph is a graph whose vertices can be partitioned into a clique and an independent vertex set.
Equivalently, it is a chordal graph whose graph complement is also chordal (Royle 2000). Royle (2000) also proved that there is a one-one correspondence between the split graphs on 
vertices and the minimal covers of a set of size 
.
Classes of graphs that are split include complete 
, empty 
, star, and sun graphs.
Since all chordal graphs are perfect, so too are all split graphs.
Let 
be the degree sequence of a graph on 
vertices, and let 
be the largest value of 
such that 
. Then the graph is a split graph iff
Furthermore, for a graph satisfying this condition, the vertices corresponding to the first 
degrees in the degree sequence correspond to a maximum clique and the remainder to an independent vertex set (Golumbic 1980, Hammer and Simeone 1981).
The numbers of simple split graphs on 
, 2, ... vertices are given by 1, 2, 4, 9, 21, 56, 164, 557, 2223, 10766, 64956, 501696, ... (OEIS A048194).
REFERENCES
Golumbic, M. C. Algorithmic Graph Theory and Perfect Graphs. New York: Academic Press, 1980.
Hammer, P. L. and Simeone, B. "The Splittance of a Graph." Combinatorica 1, 275-284, 1981.
Royle, G. F. "Counting Set Covers and Split Graphs." J. Integer Seq. 3, Article 00.2.6, 2000. https://cs.uwaterloo.ca/journals/JIS/VOL3/ROYLE/royle.html.
Sloane, N. J. A. Sequence A048194 in "The On-Line Encyclopedia of Integer Sequences."
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
