On ℓ \ell -distance-balancedness of cubic Cayley graphs of dihedral groups
2024
Read On ℓ \ell -distance-balancedness of cubic Cayley graphs of dihedral groups (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-18893.txt.
Introduction
Gang Ma and co-authors prove a 2024 result about balance in a family of cubic graphs built from dihedral groups. A graph is called distance balanced at a given length when, for any two vertices that far apart, the sets of vertices closer to one or the other are equal in size. A graph that is balanced at every length is highly distance balanced.
Cayley graphs turn group elements into vertices, with edges from a chosen generating set. The authors show that cubic Cayley graphs of dihedral groups from two named generating sets are highly distance balanced. That settles part of an open problem posed by Miklavič and Šparl. The result adds exact knowledge about symmetry in these graphs, a topic tied to network design and pure algebra.
Catalog record
| YEAR | 2024 |
|---|---|
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 24 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-18893
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On ℓ \ell -distance-balancedness of cubic Cayley graphs of dihedral groups Abstract A connected graph Γ \Gamma of diameter diam ( Γ ) ≥ ℓ {\rm diam}(\Gamma)\geq\ell is ℓ \ell -distance-balanced if | W x y ( Γ ) | = | W y x ( Γ ) | |W_{xy}(\Gamma)|=|W_{yx}(\Gamma)| for every x , y ∈ V ( Γ ) x,y\in V(\Gamma) with d Γ ( x , y ) = ℓ d_{\Gamma}(x,y)=\ell , where W x y ( Γ ) W_{xy}(\Gamma) is the set of vertices of Γ \Gamma that are closer to x x than to y y . Γ \Gamma is said to be highly distance-balanced if it is ℓ \ell -distance-balanced for every ℓ ∈ [ diam ( Γ ) ] \ell\in[{\rm diam}(\Gamma)] . It is proved that every cubic Cayley graph whose generating set is one of { a , a n − 1 , b a r } \{a,a^{n-1},ba^{r}\} and { a k , a n − k , b a t } \{a^{k},a^{n-k},ba^{t}\} is highly distance-balanced. This partially solves a problem posed by Miklavič and Šparl. Gang Ma, Jianfeng Wang 1 1 1 Corresponding author , Guang Li School of Mathematics and Statistics, Shandong University of Technology, Zibo, China math \_ [email protected] (G. Ma) [email protected] (J.F. Wang) [email protected] (G. Li) Sandi Klavžar Faculty of Mathematics and Physics, University of Ljubljana, Ljubljana, Slovenia Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia [email protected] Key words: Distance-balanced graph; \ell -distance-balanced graph; Cayley graph; Dihedral group AMS Subj. Class: 05C12, 05C25 1 Introduction If \Gamma=(V(\Gamma),E(\Gamma)) is a connected graph and x,y\in V(\Gamma) , then the distance d_{\Gamma}(x,y) between x and y is the number of edges on a shortest (x,y) -path. The diameter {\rm diam}(\Gamma) of \Gamma is the maximum distance between its vertices. The set W_{xy}(\Gamma) contains the vertices that are closer to x than to y , that is, W_{xy}(\Gamma)=\{w\in V(\Gamma):\ d_{\Gamma}(w,x)<d_{\Gamma}(w,y)\} . Vertices x and y are balanced if |W_{xy}(\Gamma)|=|W_{yx}(\Gamma)| . For an integer \ell\in[{\rm diam}(\Gamma)]=\{1,2,\ldots,{\rm diam}(\Gamma)\} we say that \Gamma is \ell - distance-balanced if each pair of vertices x,y\in V(\Gamma) with d_{\Gamma}(x,y)=\ell is balanced. \Gamma is said to be highly distance-balanced if it is \ell -distance-balanced for every \ell\in[{\rm diam}(\Gamma)] . 1 -distance-balanced graphs are simply called distance-balanced graphs. Distance-balanced graphs were first considered by Handa [ 12 ] back in 1999, while the term “distance-balanced” was proposed a decade later by Jerebic et al. in [ 14 ] . The latter paper was the trigger for intensive research of distance-balanced graphs, see [ 1 , 4 , 5 , 6 , 7 , 9 , 13 , 17 , 18 , 19 , 22 , 26 ] . Moreover, distance-balanced graphs have motivated the introduction of the hitherto much-researched Mostar index [ 2 , 8 ] and distance-unbalancedness of graphs [ 16 , 24 , 25 ] . In this context, distance-balanced graphs are the graphs with the Mostar index equal to 0. Distance-balanced graphs also coincide with “transmission regular graphs,” see the survey [ 3 ] on the latter class of graphs. In [ 10 ] , Frelih generalized distance-balanced graphs to \ell -distance-balanced graphs. Since then many researchers studied \ell -distance-balancedness of graphs from different aspects, see [ 11 , 15 , 20 , 21 , 23 ] . We emphasize that in [ 23 ] some general results on \ell -distance balanced graphs are obtained and \ell -distance-balancedness of cubic graphs and graphs of diameter at most 3 are studied. The main object of our interest in this paper is Cayley graphs, so let’s recapitulate the definitions. Let G be a finite group and let S\subseteq G be a generating subset with S=S^{-1} and not containing the identity. Then the Cayley graph \Cay(G;S) has the vertex set G , and g\in G is adjacent to h\in G whenever g^{-1}h\in S . Kutnar et al. [ 17 ] proved that every vertex-transitive graph is strongly distance-balanced. We do not give the definition of strongly distance-balancedness here, it suffices to state that, as the name suggests, every strongly distance-balanced graphs is distance-balanced. Since Cayley graphs are vertex-transitive, every Cayley graphs is hence distance-balanced. Moreover, Miklavič and Šparl [ 23 ] proved that every Cayley graph of an abelian group is highly distance-balanced. Given the above results, the question naturally arises as to what the situation is with distance-balancedness of Cayley graphs of non-abelian groups. In particular, Miklavič and Šparl posed the problem below, for which we recall that D_{n}=C_{n}\rtimes C_{2}=\langle a,b\mid a^{n}=b^{2}=1,bab=a^{-1}\rangle is the dihedral group of order 2n , where C_{n}=\langle a\rangle is a normal cyclic subgroup of D_{n} of order n . Note that D_{n}=\{1,a,\ldots,a^{n-1},b,ba,\ldots,ba^{n-1}\} . Problem 1 . [ 23 , Problem 6.7] For each Cayley graph \mathit{\Gamma} of a dihedral group determine all \ell\geq 1 such that \mathit{\Gamma} is \ell -distance-balanced. If this is too difficult in general, consider this problem for cubic Cayley graphs of dihedral groups. Our two main results which partially answer Problem 1 read as follows. Theorem 2 . If S_{1}=\{a,a^{n-1},ba^{r}\} , where 0\leq r\leq n-1 , then \Cay(D_{n};S_{1}) is highly distance-balanced. Theorem 3 . If S_{2}=\{a^{k},a^{n-k},ba^{t}\} , where 1\leq k<n/2 , (k,n)=1 , and 0\leq t\leq n-1 , then \Cay(D_{n};S_{2}) is highly distance-balanced. The Cayley graphs \Cay(D_{6};S_{1}) where S_{1}=\{a,a^{5},ba^{2}\} , and \Cay(D_{7};S_{2}) where S_{2}=\{a^{3},a^{4},ba^{5}\} , are shown in Fig. 1 . Theorems 2 and 3 are proved in Section 2 , while in the concluding section we list some open problems. 1 a a^{2} a^{3} a^{4} a^{5} b ba ba^{2} ba^{3} ba^{4} ba^{5} 1 a^{3} a^{6} a^{2} a^{5} a a^{4} b ba^{3} ba^{6} ba^{2} ba^{5} ba ba^{4} Figure 1: \Cay(D_{6};S_{1}) where S_{1}=\{a,a^{5},ba^{2}\} (above); \Cay(D_{7};S_{2}) where S_{2}=\{a^{3},a^{4},ba^{5}\} (below). 2 Proof of Theorems 2 and 3 For a non-negative integer k , we will use the notations [k]=\{1,\ldots,k\} and [k]_{0}=\{0,\ldots,k-1\} . Before proving Theorem 2 , there are three technical lemmas. Lemma 4 . In D_{n} , if i\in[n]_{0} , then (a^{i})^{-1}=a^{n-i} , (ba^{i})^{-1}=ba^{i} , and ba^{i}b=a^{-i} . Proof. Because a^{n}=b^{2}=1 , we have (a^{i})^{-1}=a^{-i}=a^{n-i} and b^{-1}=b . Since bab=a^{-1} , we have aba=b and baba=1 . Hence (ba^{i})(ba^{i})=ba^{i-1}abaa^{i-1}=ba^{i-1}ba^{i-1}=\cdots=baba=1 . So (ba^{i})^{-1}=ba^{i} . And since (ba^{i})^{-1}=ba^{i} , we get ba^{i}ba^{i}=1 and ba^{i}b=a^{-i} . ∎ Lemma 5 . If S_{1}=\{a,a^{n-1},ba^{r}\} , r\in[n]_{0} , and if i\in[n]_{0} , then in \Cay(D_{n};S_{1}) , (1) a^{i} is adjacent to a^{i-1} , a^{i+1} , and ba^{r-i} ; and (2) ba^{i} is adjacent to ba^{i-1} , ba^{i+1} , and a^{r-i} . Proof. Because (i) (a^{i-1})^{-1}a^{i}=a\in S_{1} , (ii) (a^{i+1})^{-1}a^{i}=a^{-1}=a^{n-1}\in S_{1} , and (iii) (ba^{r-i})^{-1}a^{i}=ba^{r-i}a^{i}=ba^{r}\in S_{1} , we get that a^{i} is adjacent to (i) a^{i-1} , (ii) a^{i+1} , and (iii) ba^{r-i} . By Lemma 4 we have ba^{i}b=a^{-i} . Then because (i) (ba^{i-1})^{-1}(ba^{i})=ba^{i-1}ba^{i}=a^{-(i-1)}a^{i}=a\in S_{1} , (ii) (ba^{i+1})^{-1}(ba^{i})=ba^{i+1}ba^{i}=a^{-(i+1)}a^{i}=a^{-1}=a^{n-1}\in S_{1} , and (iii) (a^{r-i})^{-1}(ba^{i})=(ba^{r-i}b)(ba^{i})=ba^{r}\in S_{1} , we can conclude that ba^{i} is adjacent to (i) ba^{i-1} , (ii) ba^{i+1} , and (iii) a^{r-i} . ∎ Lemma 6 . If S_{2}=\{a^{k},a^{n-k},b(a^{k})^{r}\} , 1\leq k<n/2 , (k,n)=1 , r\in[n]_{0} , and if i\in[n]_{0} , then in \Cay(D_{n};S_{2}) , (1) a^{ik} is adjacent to a^{(i-1)k} , a^{(i+1)k} , and ba^{(r-i)k} ;