Back to Search
Start Over
On the order of antipodal covers.
- Source :
-
Journal of Graph Theory . Feb2024, Vol. 105 Issue 2, p285-296. 12p. - Publication Year :
- 2024
-
Abstract
- A noncomplete graph G $G$ of diameter d $d$ is called an antipodal r $r$‐cover if its vertex set can be partitioned into the subsets (also called fibres) V1,V2,...,Vm ${V}_{1},{V}_{2},\ldots ,{V}_{m}$ of r $r$ vertices each, in such a way that two vertices of G $G$ are at distance d $d$ if and only if they belong to the same fibre. We say that G $G$ is symmetric if for every u∈Vi,v∈Vj $u\in {V}_{i},v\in {V}_{j}$, there exist u′∈Vi $u^{\prime} \in {V}_{i}$ such that d(u,u′)=d(u,v)+d(v,u′) $d(u,u^{\prime})=d(u,v)+d(v,u^{\prime})$, where 1≤i≠j≤m $1\le i\ne j\le m$. In this paper, we prove that, for r≥2 $r\ge 2$, an antipodal r $r$‐cover which is not a cycle, has at least r3d2 $r\unicode{x0230A}\frac{3d}{2}\unicode{x0230B}$ vertices provided d≥3 $d\ge 3$, and at least 2r(d−1) $2r(d-1)$ vertices provided it is symmetric. Our results extend those of Göbel and Veldman. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 03649024
- Volume :
- 105
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- Journal of Graph Theory
- Publication Type :
- Academic Journal
- Accession number :
- 174271742
- Full Text :
- https://doi.org/10.1002/jgt.23037