1,720,980 research outputs found
Frattini-based starters in 2-groups
No full textLet G be a group of order 2^t , with t >3. We prove a sufficient condition for the existence of a one-factorization of a completegraph, admitting G as an automorphism group acting sharply transitively on the vertex-set
1-fattorizzazioni e gruppi di automorfismi
No full textAll'aumentare del numero dei vertici del grafo completo, il numero delle 1-fattorizzazioni diventa enorme. Dare una classificazione completa delle 1-fattorizzazioni risulta molto difficile. Classificazioni parziali, ossia classificazioni basate su determinate proprietà, risultano più facili. In questa nota vengono prese in considerazione 1-fattorizzazioni con proprietà di simmetria, vale a dire 1-fattorizzazioni con un gruppo di automorfismi non banale
Starters: Doubling Constructions
No full textLet F be a one–factorization of K_2m and let H be an automorphism group of F acting sharply transitively on the vertices of K_2m. Let G be a group having H as a subgroup of index 2. We give a sufficient condition for the existence of a one–factorization of K_4m which doubles the original one-factorization F and admits G as an automorphism group acting sharply transitively on vertices
Degree- and orbit-balanced Γ-designs when Γ has five vertices
No full textA Γ-design of the complete graph Kv is a set D of subgraphs isomorphic to Γ (blocks) whose edge-sets partition the edge-set of Kv. D is balanced if the number of blocks containing x is the same number of blocks containing y for any two vertices x and y. D is orbit-balanced, or strongly balanced, if the number of blocks containing x as a vertex of a vertex-orbit A of Γ is the same number of blocks containing y as a vertex of A, for any two vertices x and y and for every vertex-orbit A of Γ. We say that D is degree-balanced if the number of blocks containing x as a vertex of degree d in Γ is the same number of blocks containing y as a vertex of degree d in Γ, for any two vertices x and y and for every degree d in Γ. An orbit-balanced Γ-design is also degree-balanced; a degree-balanced Γ-design is also balanced. The converse is not always true. We study the spectrum for orbit-balanced, degree-balanced, and balanced Γ-designs of Kv when Γ is a graph with five vertices, none of which is isolated. We also study the existence of balanced (respectively, degree-balanced) Γ-designs of Kv which are not degree-balanced (respectively, not orbit-balanced)
Octahedral, dicyclic and special linear solutions of some Hamilton-Waterloo problems
Get PDFWe give a sharply-vertex-transitive solution of each of the nine Hamilton-Waterloo problems left open by Danziger, Quattrocchi and Stevens
Symmetric bowtie decompositions of the complete graph
Get PDFGiven a bowtie decomposition of the complete graph Kvadmitting an automorphism group G acting transitively on thevertices of the graph, we give necessary conditions involvingthe rank of the group and the cycle types of the permutationsin G. These conditions yield non--existence results forinstance when G is the dihedral group of order 2v, with, or a group acting transitively on thevertices of K9 and K_{21}. Furthermore, we havenon--existence for K_{13} when the group G is differentfrom the cyclic group of order 13 or for K_{25} when thegroup G is not an abelian group of order 25. Bowtiedecompositions admitting an automorphism group whose action onvertices is sharply transitive, primitive or 1--rotational,respectively, are also studied. It is shown that if the actionof G on the vertices of K_v is sharply transitive, then theexistence of a G--invariant bowtie decomposition is excludedwhen and is equivalent to the existence ofa G--invariant Steiner triple system of order v. We arealways able to exclude existence if the action of G on thevertices of K_v is assumed to be 1--rotational. If,instead, G is assumed to act primitively then existence canbe excluded when v is a prime power satisfying someadditional arithmetic constraint
Covering cubic graphs with matchings of large size
No full textLet m be a positive integer and let G be a cubic graph of order 2n. We consider the problem of covering the edge-set of G with the minimum number of matchings of size m. This number is called the excessive [m]-index of G in the literature. The case m = n, that is, a covering with perfect matchings, is known to be strictly related to an outstanding conjecture of Berge and Fulkerson. In this paper we study in some detail the case m = n-1. We show how this parameter can be large for cubic graphs with low connectivity and we furnish some evidence that each cyclically 4-connected cubic graph of order 2n has excessive [n-1]-index at most 4. Finally, we discuss the relation between excessive [n-1]-index and some other graph parameters such as oddness and circumference
Even cycles and even 2-factors in the line graph of a simple graph
Get PDFLet G be a connected graph with an even number of edges. We show that if the subgraph of G induced by the vertices of odd degree has a perfect matching, then the line graph of G has a 2-factor whose connected components are cycles of even length (an even 2-factor). For a cubic graphG, we also give a necessary and sufficient condition so that the corresponding line graph L(G) has an even cycle decomposition of index 3, i.e., the edge-set of L(G) can be partitioned into three 2-regular subgraphs whose connected components are cycles of even length. The more general problem of the existence of even cycle decompositions of index m in 2d-regular graphs is also addressed
A novel characterization of cubic Hamiltonian graphs via the associated quartic graphs
No full textWe give a necessary and sufficient condition for a cubic graph to be Hamiltonian by analyzing Eulerian tours in certain spanning subgraphs of the quartic graph associated with the cubic graph by 1-factor contraction. This correspondence is most useful in the case when it induces a blue and red 2-factorization of the associated quartic graph. We use this condition to characterize the Hamiltonian I-graphs, a further generalization of generalized Petersen graphs. The characterization of Hamiltonian I-graphs follows from the fact that one can choose a 1-factor in any I-graph in such a way that the corresponding associated quartic graph is a graph bundle having a cycle graph as base graph and a fiber and the fundamental factorization of graph bundles playing the role of blue and red factorization. The techniques that we develop allow us to represent Cayley multigraphs of degree 4, that are associated to abelian groups, as graph bundles. Moreover, we can find a family of connected cubic (multi)graphs that contains the family of connected I-graphs as a subfamily
Minkowski tangent-circle structures and key distribution patterns
No full textKey distribution patterns are finite incidence structures satisfying certain properties which enables them to be applied to a problem in network key distribution. Few examples of key distribution patterns are known. We present new examples of finite Minkowski tangent-circle structures and show how to construct key distribution patterns from them
- …
