Neighborhood contraction in graphs

被引:1
作者
Kamath, S. S. [1 ]
Kolake, Prameela [1 ]
机构
[1] Natl Inst Technol Karnataka, Dept Math & Computat Sci, Mangalore 575025, India
关键词
Neighborhood; degree; induced subgraph; contraction; domination; MINOR THEORY;
D O I
10.1007/s13226-015-0169-9
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Let G be a graph and v be any vertex of G. Then the neighborhood contracted graph G (v) of G, with respect to the vertex v, is the graph with vertex set V - N(v), where two vertices u,w a V - N(v) are adjacent in G (v) if either w = v and u is adjacent to any vertex of N(v) in G or u,w a parts per thousand N[v] and u,w are adjacent in G. The properties of the neighborhood contracted graphs are discussed in this paper. The neighborhood contraction in some special class of graphs, the domination in a graph and the neighborhood contracted graphs are discussed in the paper.
引用
收藏
页码:97 / 110
页数:14
相关论文
共 7 条
[1]  
Bodlaender HansL., 2006, J GRAPH ALGORITHMS A, V10, P5, DOI DOI 10.7155/JGAA.00117
[2]   Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner's Contraction [J].
Demaine, Erik D. ;
Hajiaghayi, MohammadTaghi ;
Kawarabayashi, Ken-ichi .
ALGORITHMICA, 2009, 54 (02) :142-180
[3]  
Harary F., 1972, GRAPH THEORY
[4]  
Haynes T.W., 1997, FUNDAMENTALS DOMINAT
[5]   Some recent progress and applications in graph minor theory [J].
Kawarabayashi, Ken-ichi ;
Mohar, Bojan .
GRAPHS AND COMBINATORICS, 2007, 23 (01) :1-46
[6]  
Lovász L, 2006, B AM MATH SOC, V43, P75
[7]  
West D. B., 2003, Introduction to Graph Theory