ǂA ǂcomplete classification of cubic symmetric graphs of girth 6
Povzetek
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$▫.
Ključne besede
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;
Podatki
| Jezik: | Angleški jezik |
|---|---|
| Leto izida: | 2009 |
| Tipologija: | 1.01 - Izvirni znanstveni članek |
| Organizacija: | UP - Univerza na Primorskem |
| UDK: | 519.17 |
| COBISS: |
2724823
|
| ISSN: | 0095-8956 |
| Št. ogledov: | 3842 |
| Št. prenosov: | 86 |
| Ocena: | 0 (0 glasov) |
| Metapodatki: |
|
Ostali podatki
| Sekundarni jezik: | Angleški jezik |
|---|---|
| Sekundarne ključne besede: | teorija grafov;kubični grafi;simetrični grafi;▫$s$▫-regularni grafi;dolžina najkrajšega cikla; |
| Vrsta dela (COBISS): | Delo ni kategorizirano |
| Strani: | str. 162-184 |
| Letnik: | ǂVol. ǂ99 |
| Zvezek: | ǂNo. ǂ1 |
| Čas izdaje: | 2009 |
| Ključne besede (UDK): | mathematics;natural sciences;naravoslovne vede;matematika;mathematics;matematika;combinatorial analysis;graph theory;kombinatorika; |
| DOI: | 10.1016/j.jctb.2008.06.001 |
| ID: | 1471792 |
Priporočena dela:
ǂA ǂcomplete classification of cubic symmetric graphs of girth 6
2009,
ni podatka o podnaslovu
On 2-fold covers of graphs
2008,
ni podatka o podnaslovu
Consistent Cycles in 1/2-Arc-Transitive Graphs
2009,
ni podatka o podnaslovu
On cubic symmetric graphs of girth 6
2007,
Combinatorics Seminar, 30.5.2007, Ohio State University, Columbus, Ohio, USA
On generalized Cayley graphs
2013,
ni podatka o podnaslovu