INTERSECTION-PROPERTIES OF GRAPHS

被引：0
作者：
MCKEE, TA
机构：
[1] Department of Mathematics and Statistics, Wright State University, Dayton
来源：
DISCRETE MATHEMATICS | 1991年 / 89卷 / 03期
关键词：
D O I：
10.1016/0012-365X(91)90118-L
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
For each graph-theoretic property, we define a corresponding 'intersection property', motivated by the natural relationship of paths with interval graphs, and of trees with chordal graphs. We then develop a simple formal language, based on vertices and paths, which supports transfer of selected information about the original property to its intersection property. For instance, a simple description of paths produces the asteroidal triple characterization of interval graphs.
引用
收藏
页码：253 / 260
页数：8
相关论文
共 50 条
[21]   Intersection properties of line graphs [J].
Discrete Math, 1-3 (33)
[22]   Intersection properties of line graphs [J].
Bylka, S ;
Komar, J .
DISCRETE MATHEMATICS, 1997, 164 (1-3) :33-45
[23]   INTERSECTION-PROPERTIES OF BALLS IN TENSOR-PRODUCTS OF SOME BANACH-SPACES [J].
RAO, TSSRK ;
ROY, AK ;
SUNDARESAN, K .
MATHEMATICA SCANDINAVICA, 1989, 65 (01) :103-118
[24]   INTERSECTION-PROPERTIES OF BALLS IN TENSOR-PRODUCTS OF SOME BANACH-SPACES .2. [J].
RAO, TSSRK .
INDIAN JOURNAL OF PURE & APPLIED MATHEMATICS, 1990, 21 (03) :275-284
[25]   Turan and Ramsey Properties of Subcube Intersection Graphs [J].
Johnson, J. Robert ;
Markstrom, Klas .
COMBINATORICS PROBABILITY & COMPUTING, 2013, 22 (01) :55-70
[26]   Selected Combinatorial Properties of Random Intersection Graphs [J].
Nikoletseas, Sotiris ;
Raptopoulos, Christoforos ;
Spirakis, Paul G. .
ALGEBRAIC FOUNDATIONS IN COMPUTER SCIENCE: ESSAYS DEDICATED TO SYMEON BOZAPALIDIS ON THE OCCASION OF HIS RETIREMENT, 2011, 7020 :347-362
[27]   The Liouville and the intersection properties are equivalent for planar graphs [J].
Benjamini, Itai ;
Curien, Nicolas ;
Georgakopoulos, Agelos .
ELECTRONIC COMMUNICATIONS IN PROBABILITY, 2012, 17 :1-5
[28]   Expander properties and the cover time of random intersection graphs [J].
Nikoletseas, S. ;
Raptopoulos, C. ;
Spirakis, P. G. .
THEORETICAL COMPUTER SCIENCE, 2009, 410 (50) :5261-5272
[29]   Expander properties and the cover time of random intersection graphs [J].
Nikoletseas, Sotiris E. ;
Raptopoulos, Christoforos ;
Spirakis, Paul G. .
MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2007, PROCEEDINGS, 2007, 4708 :44-+
[30]   Maximum Cliques in Graphs with Small Intersection Number and Random Intersection Graphs [J].
Nikoletseas, Sotiris ;
Raptopoulos, Christoforos ;
Spirakis, Paul G. .
MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2012, 2012, 7464 :728-739
12345