ǂA ǂcomplete classification of cubic symmetric graphs of girth 6
Abstract
A complete classification of cubic symmetric graphs of girth 6 is given. It is shown that with the exception of the Heawood graph, the Moebius-Kantor graph, the Pappus graph, and the Desargues graph, a cubic symmetric graph ▫$X$▫ of girth 6 is a normal Cayley graph of a generalized dihedral group; in particular, (i) ▫$X$▫ is 2-regular if and only if it is isomorphic to a so-called ▫$I_k^n$▫-path, a graph of order either ▫$n^2/2$▫ or ▫$n^2/6$▫, which is characterized by the fact that its quotient relative to a certain semiregular automorphism is a path. (ii) ▫$X$▫ is 1-regular if and only if there exists an integer ▫$r$▫ with prime decomposition ▫$r=3^s p_1^{e_1} \dots p_t^{e_t} > 3$▫, where ▫$s \in \{0,1\}$▫, ▫$t \ge 1$▫, and ▫$p_i \equiv 1 \pmod{3}$▫, such that ▫$X$▫ is isomorphic either to a Cayley graph of a dihedral group ▫$D_{2r}$▫ of order ▫$2r$▫ or ▫$X$▫ is isomorphic to a certain ▫$\ZZ_r$▫-cover of one of the following graphs: the cube ▫$Q_3$▫, the Pappus graph or an ▫$I_k^n(t)$▫-path of order ▫$n^2/2$▫.
Keywords
teorija grafov;kubični grafi;simetrični grafi;▫$s$▫-regularni grafi;dolžina najkrajšega cikla;graph theory;cubic graphs;symmetric graphs;▫$s$▫-regular graphs;girth;consistent cycle;
Data
| Language: | English |
|---|---|
| Year of publishing: | 2009 |
| Typology: | 1.01 - Original Scientific Article |
| Organization: | UP - University of Primorska |
| UDC: | 519.17 |
| COBISS: |
2724823
|
| ISSN: | 0095-8956 |
| Views: | 3842 |
| Downloads: | 86 |
| Average score: | 0 (0 votes) |
| Metadata: |
|
Other data
| Secondary language: | English |
|---|---|
| Secondary keywords: | teorija grafov;kubični grafi;simetrični grafi;▫$s$▫-regularni grafi;dolžina najkrajšega cikla; |
| Type (COBISS): | Not categorized |
| Pages: | str. 162-184 |
| Volume: | ǂVol. ǂ99 |
| Issue: | ǂNo. ǂ1 |
| Chronology: | 2009 |
| Keywords (UDC): | mathematics;natural sciences;naravoslovne vede;matematika;mathematics;matematika;combinatorial analysis;graph theory;kombinatorika; |
| DOI: | 10.1016/j.jctb.2008.06.001 |
| ID: | 1471792 |
Recommended works:
ǂA ǂcomplete classification of cubic symmetric graphs of girth 6
2009,
no subtitle data available
On 2-fold covers of graphs
2008,
no subtitle data available
Consistent Cycles in 1/2-Arc-Transitive Graphs
2009,
no subtitle data available
On cubic symmetric graphs of girth 6
2007,
Combinatorics Seminar, 30.5.2007, Ohio State University, Columbus, Ohio, USA
On generalized Cayley graphs
2013,
no subtitle data available