241. Asymptotic automorphism groups of Cayley digraphs and graphs of abelian groups of prime-power orderEdward Dobson, 2010, original scientific article Abstract: We show that almost every Cayley graph ▫$\Gamma$▫ of an abelian group ▫$G$▫ of odd prime-power order has automorphism group as small as possible. Additionally, we show that almost every Cayley (di)graph ▫$\Gamma$▫ of an abelian group ▫$G$▫ of odd prime-power order that does not have automorphism group as small as possible is a normal Cayley (di)graph of ▫$G$▫ (that is, ▫$G_L \triangleleft {\rm Aut}(\Gamma))$▫.
Keywords: mathematics, graph theory, Cayley graph, abelian group, automorphism group, asymptotic, ▫$p$▫-group
Published in RUP: 15.10.2013; Views: 4646; Downloads: 137
 Link to full text |
242. On 2-fold covers of graphsYan-Quan Feng, Klavdija Kutnar, Aleksander Malnič, Dragan Marušič, 2008, original scientific article Abstract: A regular covering projection ▫$\wp : \widetilde{X} \to X$▫ of connected graphs is ▫$G$▫-admissible if ▫$G$▫ lifts along ▫$\wp$▫. Denote by ▫$\tilde{G}$▫ the lifted group, and let CT▫$(\wp)$▫ be the group of covering transformations. The projection is called ▫$G$▫-split whenever the extension ▫{$\mathrm{CT}}(\wp) \to \tilde{G} \to G$▫ splits. In this paper, split 2-covers are considered, with a particular emphasis given to cubic symmetric graphs. Supposing that ▫$G$▫ is transitive on ▫$X$▫, a ▫$G$▫-split cover is said to be ▫$G$▫-split-transitive if all complements ▫$\tilde{G} \cong G$▫ of CT▫$(\wp)$▫ within ▫$\tilde{G}$▫ are transitive on ▫$\widetilde{X}$▫; it is said to be ▫$G$▫-split-sectional whenever for each complement ▫$\tilde{G}$▫ there exists a ▫$\tilde{G}$▫-invariant section of ▫$\wp$▫; and it is called ▫$G$▫-split-mixed otherwise. It is shown, when ▫$G$▫ is an arc-transitive group, split-sectional and split-mixed 2-covers lead to canonical double covers. Split-transitive covers, however, are considerably more difficult to analyze. For cubic symmetric graphs split 2-cover are necessarily canonical double covers (that is, no ▫$G$▫-split-transitive 2-covers exist) when ▫$G$▫ is 1-regular or 4-regular. In all other cases, that is, if ▫$G$▫ is ▫$s$▫-regular, ▫$s=2,3$▫ or ▫$5$▫, a necessary and sufficient condition for the existence of a transitive complement ▫$\tilde{G}$▫ is given, and moreover, an infinite family of split-transitive 2-covers based on the alternating groups of the form ▫$A_{12k+10}$▫ is constructed. Finally, chains of consecutive 2-covers, along which an arc-transitive group ▫$G$▫ has successive lifts, are also considered. It is proved that in such a chain, at most two projections can be split. Further, it is shown that, in the context of cubic symmetric graphs, if exactly two of them are split, then one is split-transitive and the other one is either split-sectional or split-mixed.
Keywords: graph theory, graphs, cubic graphs, symmetric graphs, ▫$s$▫-regular group, regular covering projection
Published in RUP: 15.10.2013; Views: 3693; Downloads: 34
Link to full text |
243. |
244. |
245. A note on domination and independence-domination numbers of graphsMartin Milanič, 2013, published scientific conference contribution Abstract: Vizing's conjecture is true for graphs ▫$G$▫ satisfying ▫$\gamma^i(G) = \gamma(G)$▫, where ▫$\gamma(G)$▫ is the domination number of a graph ▫$G$▫ and ▫$\gamma^i(G)$▫ is the independence-domination number of ▫$G$▫, that is, the maximum, over all independent sets ▫$I$▫ in ▫$G$▫, of the minimum number of vertices needed to dominate ▫$I$▫. The equality ▫$\gamma^i(G) = \gamma(G)$▫ is known to hold for all chordal graphs and for chordless cycles of length ▫$0 \pmod{3}$▫. We prove some results related to graphs for which the above equality holds. More specifically, we show that the problems of determining whether ▫$\gamma^i(G) = \gamma(G) = 2$▫ and of verifying whether ▫$\gamma^i(G) \ge 2$▫ are NP-complete, even if ▫$G$▫ is weakly chordal. We also initiate the study of the equality ▫$\gamma^i = \gamma$▫ in the context of hereditary graph classes and exhibit two infinite families of graphs for which ▫$\gamma^i < \gamma$▫.
Keywords: Vizing's conjecture, domination number, independence-domination number, weakly chordal graph, NP-completeness, hereditary graph class, IDD-perfect graph
Published in RUP: 15.10.2013; Views: 3108; Downloads: 128
 Full text (300,57 KB) |
246. Distance-regular Cayley graphs on dihedral groupsŠtefko Miklavič, Primož Potočnik, 2007, original scientific article Abstract: The main result of this article is a classification of distance-regular Cayley graphs on dihedral groups. There exist four obvious families of such graphs, which are called trivial. These are: complete graphs, complete bipartite graphs, complete bipartite graphs with the edges of a 1-factor removed, and cycles. It is proved that every non-trivial distance-regular Cayley graph on a dihedral group is bipartite, non-antipodal, has diameter 3 and arises either from a cyclic di#erence set, or possibly (if any such exists) from a dihedral difference set satisfying some additional conditions. Finally, all distance-transitive Cayley graphs on dihedral groups are determined. It transpires that a Cayley graph on a dihedral group is distance-transitive if and only if it is trivial, or isomorphic to the incidence or to the non-incidence graph of a projective space ▫$\mathrm{PG}_{d-1} (d,q)$▫, ▫$d \ge 2$▫, or the unique pair of complementary symmetric designs on 11 vertices.
Keywords: mathematics, grah theory, distance-regular graph, distance-transitive graph, Cayley graph, dihedral group, dihedrant, difference set
Published in RUP: 15.10.2013; Views: 3095; Downloads: 99
Link to full text |
247. |
248. |
249. |
250. |
