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

David Auger; Irne Charon; Olivier Hudry; Antoine Lobstein

doi:10.1016/j.dam.2011.04.010

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

David Auger
, Irne Charon
, Olivier Hudry
, Antoine Lobstein

Research output: Contribution to journal › Article › peer-review

Abstract

Let G be an undirected graph and ^Gr be its r-th power. We study different issues dealing with the number of edges in G and ^Gr. In particular, we answer the following question: given an integer r<2 and all connected graphs G of order n such that ^Gr≠^Kn, what is the minimum number of edges that are added when going from G to ^Gr, and which are the graphs achieving this bound?

Original language	English
Pages (from-to)	1666-1675
Number of pages	10
Journal	Discrete Applied Mathematics
Volume	159
Issue number	16
DOIs	https://doi.org/10.1016/j.dam.2011.04.010
Publication status	Published - 28 Sept 2011

Keywords

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

Access to Document

10.1016/j.dam.2011.04.010

Cite this

@article{5949b3439a2f4bd5b2a922cfb809501c,

title = "On the sizes of graphs and their powers: The undirected case",

abstract = "Let G be an undirected graph and Gr be its r-th power. We study different issues dealing with the number of edges in G and Gr. In particular, we answer the following question: given an integer r<2 and all connected graphs G of order n such that Gr≠Kn, what is the minimum number of edges that are added when going from G to Gr, and which are the graphs achieving this bound?",

keywords = "Diameter, Edge number, Graph theory, Hamiltonian graph, Identifying code, Power of a graph, Size of a graph, Transitive closure of a graph, Undirected graph",

author = "David Auger and Irne Charon and Olivier Hudry and Antoine Lobstein",

year = "2011",

month = sep,

day = "28",

doi = "10.1016/j.dam.2011.04.010",

language = "English",

volume = "159",

pages = "1666--1675",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

number = "16",

}

TY - JOUR

T1 - On the sizes of graphs and their powers

T2 - The undirected case

AU - Auger, David

AU - Charon, Irne

AU - Hudry, Olivier

AU - Lobstein, Antoine

PY - 2011/9/28

Y1 - 2011/9/28

N2 - Let G be an undirected graph and Gr be its r-th power. We study different issues dealing with the number of edges in G and Gr. In particular, we answer the following question: given an integer r<2 and all connected graphs G of order n such that Gr≠Kn, what is the minimum number of edges that are added when going from G to Gr, and which are the graphs achieving this bound?

AB - Let G be an undirected graph and Gr be its r-th power. We study different issues dealing with the number of edges in G and Gr. In particular, we answer the following question: given an integer r<2 and all connected graphs G of order n such that Gr≠Kn, what is the minimum number of edges that are added when going from G to Gr, and which are the graphs achieving this bound?

KW - Diameter

KW - Edge number

KW - Graph theory

KW - Hamiltonian graph

KW - Identifying code

KW - Power of a graph

KW - Size of a graph

KW - Transitive closure of a graph

KW - Undirected graph

UR - https://www.scopus.com/pages/publications/80051792664

U2 - 10.1016/j.dam.2011.04.010

DO - 10.1016/j.dam.2011.04.010

M3 - Article

AN - SCOPUS:80051792664

SN - 0166-218X

VL - 159

SP - 1666

EP - 1675

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 16

ER -

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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this