Extremal values for the maximum degree in a twin-free graph

Irène Charon, Olivier Hudry, Antoine Lobstein

Research output: Contribution to journalArticlepeer-review

Abstract

Consider a connected undirected graph G = (V, E) and an integer r ≥ 1; for any vertex v ε V, let Br(v) denote the ball of radius r centred at v, i.e., the set of all vertices linked to v by a path of at most r edges. If for all vertices v ε V, the sets Br(v) are different, then we say that G is r-twin-free. In r-twin-free graphs, we prolong the study of the extremal values that can be reached by some classical parameters in graph theory, and investigate here the maximum degree.

Original languageEnglish
Pages (from-to)257-274
Number of pages18
JournalArs Combinatoria
Volume107
Publication statusPublished - 1 Jan 2012

Keywords

  • Graph theory
  • Identifying codes
  • Maximum degree
  • Twins

Fingerprint

Dive into the research topics of 'Extremal values for the maximum degree in a twin-free graph'. Together they form a unique fingerprint.

Cite this