The Construction of two classes of 4-valent triCayley Graphs over Cyclic Group

Xiaohan Ye, H.m. ZhangInternational Journal of Mathematical Sciences and Computing 2024 · DOI

Abstract

The symmetry of the graph has always been a hot topic in graph theory and the vertex-transitive graphs are a class of graphs with high symmetry. Cayley graphs which are the highly symmetrical graphs play an important role and much work has been done in the study. The tri-Cayley graph is a natural generalization of the Cayley graph. A graph is said to be a tri-Cayley graph if it admits a semiregular subgroup of automorphisms having three orbits of equal length. Koács et al. classified the cubic symmetric tricirculants in 2012 and Potoānik et al. classified the cubic vertex-transitive tricirculants in 2018. Currently, there is no research on the classification of 4-valent tri-Cayley graphs over cyclic group. In this paper, we will construct two classes of 4-valent tri-Cayley graphs over cyclic group and discuss their automorphism groups. In addition, the vertex transitivity, edge transitivity and arc transitivity are proved.

Introduction

Symmetry is a fundamental property in graph theory, often dictating the efficiency and robustness of network topologies. Vertex-transitive graphs, where every vertex is structurally identical to every other, represent a high degree of symmetry. Cayley graphs, constructed from groups, are the standard-bearers for such properties.

A tri-Cayley graph is a natural generalization, defined by a semiregular subgroup of automorphisms that partitions the vertex set into three orbits of equal length. While cubic (3-valent) tri-Cayley graphs have been extensively classified, 4-valent variants over cyclic groups have remained largely unstudied. This paper fills this gap by constructing two specific classes of 4-valent tri-Cayley graphs and analyzing their symmetry characteristics.

Construction Methodology

The researchers utilized algebraic graph theory to define two distinct classes of graphs, $X_1$ and $X_2$, over a cyclic group $G$.

  1. Class $X_1$ (0-type): This construction features empty internal connection sets ($A_i = \emptyset$), meaning no edges exist within a single orbit. All connectivity is established between the three distinct orbits.
  2. Class $X_2$ (2-type): In contrast, this class includes internal connections within the orbits, creating a more complex local structure.
A visual representation of a complex 4-valent tri-Cayley graph construction over a cyclic group.

Symmetry Analysis: Transitivity and Automorphisms

A central contribution of this work is the rigorous proof of the transitivity properties of these graphs. By explicitly calculating the full automorphism groups, the authors demonstrate that both $X_1$ and $X_2$ are vertex-transitive. This implies that for any two vertices in the graph, there exists a symmetry operation that maps one to the other.

However, the study reveals that high vertex symmetry does not necessarily extend to edges or arcs. The researchers proved that these graphs are neither edge-transitive nor arc-transitive. The proof hinges on the analysis of 3-cycles (triangles). In the constructed graphs, some edges are part of a triangle while others are not. Since an automorphism must preserve such local structures, an edge within a triangle cannot be mapped to one outside of it, thereby precluding edge-transitivity.

Diagram illustrating the local connectivity and orbit structure of the tri-Cayley graph.

Conclusion

This research provides a foundational step toward the full classification of 4-valent tri-Cayley graphs. By demonstrating that vertex-transitivity can be maintained in 4-valent structures over cyclic groups without requiring edge-transitivity, the authors highlight the nuanced complexity of generalized Cayley graphs. Future work will aim to extend these constructions to non-abelian groups and pursue a comprehensive classification of all such 4-valent structures.

Summary updated

Abstract

The symmetry of the graph has always been a hot topic in graph theory and the vertex-transitive graphs are a class of graphs with high symmetry. Cayley graphs which are the highly symmetrical graphs play an important role and much work has been done in the study. The tri-Cayley graph is a natural generalization of the Cayley graph. A graph is said to be a tri-Cayley graph if it admits a semiregular subgroup of automorphisms having three orbits of equal length. Koács et al. classified the cubic symmetric tricirculants in 2012 and Potočnik et al. classified the cubic vertex-transitive tricirculants in 2018. Currently, there is no research on the classification of 4-valent tri-Cayley graphs over cyclic group. In this paper, we will construct two classes of 4-valent tri-Cayley graphs over cyclic group and discuss their automorphism groups. In addition, the vertex transitivity, edge transitivity and arc transitivity are proved.
BibTeX
@article{ye2024construction,
  author = {Xiaohan Ye and H.M. Zhang},
  title = {{The Construction of two classes of 4-valent triCayley Graphs over Cyclic Group}},
  journal = {International Journal of Mathematical Sciences and Computing},
  year = {2024},
  doi = {10.5815/ijmsc.2024.01.01},
}
Figure