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

CNRS
CNRS LTCI

Résultats de recherche: Contribution à un journal › Article › Revue par des pairs

Résumé

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?

langue originale	Anglais
Pages (de - à)	1666-1675
Nombre de pages	10
journal	Discrete Applied Mathematics
Volume	159
Numéro de publication	16
Les DOIs	https://doi.org/10.1016/j.dam.2011.04.010
état	Publié - 28 sept. 2011

Accès au document

10.1016/j.dam.2011.04.010

Contient cette citation

@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",

publisher = "Elsevier B.V.",

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

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

Résumé

Accès au document

Empreinte digitale

Contient cette citation