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 language | English |
|---|---|
| Pages (from-to) | 97-114 |
| Number of pages | 18 |
| Journal | Advances in Mathematics of Communications |
| Volume | 3 |
| Issue number | 1 |
| DOIs | |
| Publication status | Published - 1 Feb 2009 |
Keywords
- Diameter
- Graph theory
- Identifiable graph
- Identifying code
- Maximum independent set
- Maximum stable set
- Minimum degree
- Radius
- Twin-free graph
- Twins