Odd twists on strongly chordal graphs

被引：0

作者：

McKee, Terry A. ^{[1
]}

机构：

[1] Wright State Univ, Dept Math & Stat, Dayton, OH 45435 USA

来源：

DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS | 2019年 / 11卷 / 03期

关键词：

Strongly chordal graph; k-sun; uncrossed chord;

D O I：

10.1142/S1793830919500344

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Strongly chordal graphs can be characterized as chordal graphs in which every even cycle of length at least 6 has an odd chord (a chord whose endpoints are an odd distance apart in the cycle subgraph). Define "oddly chordal graphs" to be chordal graphs in which every odd cycle of length at least 7 has an odd chord. Strongly chordal graphs are shown to be oddly chordal, and the oddly chordal graphs are characterized by forbidding induced "double k-sun" subgraphs. Both strongly chordal and oddly chordal graphs are also characterized in terms of uncrossed chords of appropriate-length cycles.

引用

页数：7

共 8 条

[1]

Brandstadt A., 1999, Graph classes: A survey

[2] THE K-DOMINATION AND K-STABILITY PROBLEMS ON SUN-FREE CHORDAL GRAPHS [J].

CHANG, GJ ;

NEMHAUSER, GL .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1984, 5 (03) :332-345

[3] A characterization of strongly chordal graphs [J].

Dahlhaus, E ;

Manuel, PD ;

Miller, M .

DISCRETE MATHEMATICS, 1998, 187 (1-3) :269-271

[4] MAXCLIQUE AND UNIT DISK CHARACTERIZATIONS OF STRONGLY CHORDAL GRAPHS [J].

De Caria, Pablo ;

McKee, Terry A. .

DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2014, 34 (03) :593-602

[5] CHARACTERIZATIONS OF STRONGLY CHORDAL GRAPHS [J].

FARBER, M .

DISCRETE MATHEMATICS, 1983, 43 (2-3) :173-189

[6]

McKee T. A., UTIL MATH

[7] A new characterization of strongly chordal graphs [J].

McKee, TA .

DISCRETE MATHEMATICS, 1999, 205 (1-3) :245-247

[8] THE i-CHORDS OF CYCLES AND PATHS [J].

McKee, Terry A. .

DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2012, 32 (04) :607-615

← 1 →