Edge number, minimum degree, maximum independent set, radius and diameter in twin-free graphs

  • David Auger
  • , Irène Charon
  • , Iiro Honkala
  • , 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, let Br(ν) denote the ball of radius r centred at ν, i.e., the set of all vertices linked to ν by a path consisting of at most r edges. If for all vertices ν ∈ V, the sets Br(ν) 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 achieved by the main classical parameters in graph theory, and investigate here the number of edges, the minimum degree, the size of a maximum independent set, as well as radius and diameter.

Original languageEnglish
Pages (from-to)97-114
Number of pages18
JournalAdvances in Mathematics of Communications
Volume3
Issue number1
DOIs
Publication statusPublished - 1 Feb 2009

Keywords

  • Diameter
  • Graph theory
  • Identifiable graph
  • Identifying code
  • Maximum independent set
  • Maximum stable set
  • Minimum degree
  • Radius
  • Twin-free graph
  • Twins

Fingerprint

Dive into the research topics of 'Edge number, minimum degree, maximum independent set, radius and diameter in twin-free graphs'. Together they form a unique fingerprint.

Cite this