Neighborhood contraction in graphs

被引：0

作者：

S. S. Kamath

Prameela Kolake

机构：

[1] National Institute of Technology Karnataka,Department of Mathematical and Computational Sciences

来源：

Indian Journal of Pure and Applied Mathematics | 2016年 / 47卷

关键词：

Neighborhood; degree; induced subgraph; contraction; domination;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

Let G be a graph and v be any vertex of G. Then the neighborhood contracted graphGv of G, with respect to the vertex v, is the graph with vertex set V − N(v), where two vertices u,w ∈ V − N(v) are adjacent in Gv if either w = v and u is adjacent to any vertex of N(v) in G or u,w ∉ 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

页数：13

共 5 条

[1]

Bodlaender H. L.(2006)Thomas Wolle and Arie M. C. A. Koster, Contraction and treewidth lower bounds J. Graph Algorithms Appl. 10 5-49

[2]

Demaine E. D.(2009)Mohammad Taghi Hajiaghayi and Ken-ichi Kawarabayashi, Algorithmic graph minor theory: improved grid minor bounds and Wagner’s contraction Algorithmica 54 142-180

[3]

Kawarabayashi K.-i.(2007)Some recent progress and applications in graph minor theory Graphs Combin. 23 1-46

[4]

Mohar B.(2006)Graph minor theory Bull. Amer. Math. Soc. (N.S.) 43 75-86

[5]

Lovász L.(undefined)undefined undefined undefined undefined-undefined

← 1 →