On the sizes of graphs and their powers: The undirected case

被引：1

作者：

Auger, David ^{[1
,2
]}

Charon, Irene ^{[1
,2
]}

Hudry, Olivier ^{[1
,2
]}

Lobstein, Antoine ^{[2
]}

机构：

[1] Telecom ParisTech, Inst Telecom, F-75634 Paris 13, France

[2] CNRS, LTCI UMR 5141, F-75634 Paris 13, France

来源：

DISCRETE APPLIED MATHEMATICS | 2011年 / 159卷 / 16期

关键词：

Graph theory; Undirected graph; Diameter; Power of a graph; Transitive closure of a graph; Edge number; Size of a graph; Identifying code; Hamiltonian graph;

D O I：

10.1016/j.dam.2011.04.010

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Let G be an undirected graph and G(r) be its r-th power. We study different issues dealing with the number of edges in G and G(r). In particular, we answer the following question: given an integer r >= 2 and all connected graphs G of order n such that G(r) not equal K(n), what is the minimum number of edges that are added when going from G to G(r), and which are the graphs achieving this bound? (C) 2011 Elsevier B.V. All rights reserved.

引用

页码：1666 / 1675

页数：10

共 14 条

[1] Aingworth D, 1998, UTILITAS MATHEMATICA, V54, P223
[2] [Anonymous], 2001, Digraphs: theory, algorithms and applications
[3] [Anonymous], 1990, Distance in Graphs
[4] Auger D, 2010, AUSTRALAS J COMB, V48, P87
[5] Berge C., 1983, Graphes
[6] Extremal cardinalities for identifying and locating-dominating codes in graphs
Charon, Irene
Hudry, Olivier
Lobstein, Antoine
[J]. DISCRETE MATHEMATICS, 2007, 307 (3-5) : 356 - 366
[7] Diestel R., 2005, GRAPH THEORY, VThird
[8] Erds P., 1966, studia sci. Math. Hungar., V1, P215
[9] Fleischner H., 1974, Journal of Combinatorial Theory, Series B, V16, P29, DOI 10.1016/0095-8956(74)90091-4
[10] Füredi Z, 1998, GRAPH COMBINATOR, V14, P345

← 1 2 →