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

doi:10.3934/amc.2009.3.97

Article Contents

2009, Volume 3, Issue 1: 97-114. Doi: 10.3934/amc.2009.3.97

This issue Previous Article The two covering radius of the two error correcting BCH code Next Article

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

1.
Institut TELECOM - TELECOM ParisTech, & Centre National de la Recherche Scientifique - LTCI UMR 5141, 46, rue Barrault, 75634 Paris Cedex 13
2.
Department of Mathematics, University of Turku, 20014 Turku

Received: October 31, 2008

Revised: December 31, 2008

Published: January 2009

Abstract Related Papers Cited by

Abstract

Consider a connected, undirected graph $G=(V,E)$ and an integer $r \geq 1$; for any vertex $v\in V$, let $B_r(v)$ denote the ball of radius $r$ centred at $v$, i.e., the set of all vertices linked to $v$ by a path consisting of at most $r$ edges. If for all vertices $v \in V$, the sets $B_r(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 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.

Keywords:

Mathematics Subject Classification: Primary: 05C99; Secondary: 05C35.

Citation:

Article Metrics

HTML views() PDF downloads(111) Cited by(0)

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

Abstract

Access History

Article Metrics

Access History

Other Articles By Authors

Catalog

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

Abstract

Access History

SHARE

Article Metrics

Access History

Other Articles By Authors

Catalog

Export File

Citation

Format

Content