# Simona BONVICINI

Department of Physics, Informatics and Mathematics

Rinaldi, Gloria; Bonvicini, Simona ( 2018 ) - Indecomposable 1-factorizations of the complete multigraph λK2n for every λ≤2n - JOURNAL OF COMBINATORIAL DESIGNS - n. volume 26 - pp. da 12 a 26 ISSN: 1063-8539 [Articolo in rivista (262) - Articolo su rivista]
Abstract

A 1-factorization of the complete multigraph λK2n is said to be indecomposable if it cannot be represented as the union of 1-factorizations of λ0K2n and (λ - λ0)K2n, where λ0 < λ. It is said to be simple if no 1-factor is repeated. For every n ≥ 9 and for every (n - 2)/3 ≤ λ ≤ 2n, we construct an indecomposable 1-factorization of λK2n, which is not simple. These 1-factorizations provide simple and indecomposable 1-factorizations of λK2s for every s ≥ 18 and 2 ≤ λ ≤ 2└s/2┘ - 1. We also give a generalization of a result by Colbourn et al., which provides a simple and indecomposable 1-factorization of λK2n, where 2n = pm + 1, λ = (pm - 1)/2, p prime.

Bonvicini, Simona; Buratti, Marco ( 2018 ) - Octahedral, dicyclic and special linear solutions of some Hamilton-Waterloo problems - ARS MATHEMATICA CONTEMPORANEA - n. volume 14 - pp. da 1 a 14 ISSN: 1855-3966 [Articolo in rivista (262) - Articolo su rivista]
Abstract

We give a sharply-vertex-transitive solution of each of the nine Hamilton-Waterloo problems left open by Danziger, Quattrocchi and Stevens.

Bonvicini, Simona; Pisanski, Tomaž ( 2017 ) - A novel characterization of cubic Hamiltonian graphs via the associated quartic graphs - ARS MATHEMATICA CONTEMPORANEA - n. volume 12 - pp. da 1 a 24 ISSN: 1855-3966 [Articolo in rivista (262) - Articolo su rivista]
Abstract

We 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.

Bonisoli, Arrigo; Bonvicini, Simona ( 2017 ) - Even cycles and even 2-factors in the line graph of a simple graph - ELECTRONIC JOURNAL OF COMBINATORICS - n. volume 24 [Articolo in rivista (262) - Articolo su rivista]
Abstract

Let 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.

Bonisoli, Arrigo; Bonvicini, Simona; Mazzuoccolo, Giuseppe ( 2017 ) - On the palette index of a graph: the case of trees - LECTURE NOTES OF SEMINARIO INTERDISCIPLINARE DI MATEMATICA - n. volume 14 - pp. da 49 a 55 ISSN: 2284-0206 [Articolo in rivista (262) - Articolo su rivista]
Abstract

The palette of a vertex v of a graph G in a proper edge-coloring is the set of colors assigned to the edges which are incident with v. The palette index of G is the minimum number of palettes occurring among all proper edge-colorings of G. After reviewing some results on the palette index of regular graphs, we consider the problem of determining the palette index for non-regular graphs. We begin by considering the family of trees. We give an upper bound for the palette index of a tree in terms of the maximum degree Δ. We show that this bound is best possible by producing, for each Δ≥ 3, a tree T^ Δ whose palette index reaches the upper bound.

Bonvicini, Simona; Mazzuoccolo, G. ( 2016 ) - Edge-colorings of 4-regular graphs with the minimum number of palettes - GRAPHS AND COMBINATORICS - n. volume 32 - pp. da 1293 a 1311 ISSN: 0911-0119 [Articolo in rivista (262) - Articolo su rivista]
Abstract

A proper edge-coloring of a graph G is an assignment of colors to the edges of G such that adjacent edges receive distinct colors. A proper edge-coloring defines at each vertex the set of colors of its incident edges. Following the terminology introduced by Horňák, Kalinowski, Meszka and Woźniak, we call such a set of colors the palette of the vertex. What is the minimum number of distinct palettes taken over all proper edge-colorings of G? A complete answer is known for complete graphs and cubic graphs. We study in some detail the problem for 4-regular graphs.

Bonisoli, Arrigo; Bonvicini, Simona ( 2014 ) - On the existence spectrum for sharply transitive G-designs, G a [k]-matching - DISCRETE MATHEMATICS - n. volume 332 - pp. da 60 a 68 ISSN: 0012-365X [Articolo in rivista (262) - Articolo su rivista]
Abstract

In this paper we consider decompositions of the complete graph Kv into matchings of uniform cardinality k. They can only exist when k is an admissible value, that is a divisor of v(v−1)/2 with 1≤k≤v/2. The decompositions are required to admit an automorphism group Γ acting sharply transitively on the set of vertices. Here Γ is assumed to be either non-cyclic abelian or dihedral and we obtain necessary conditions for the existence of the decomposition when k is an admissible value with 1<k<v/2. Differently from the case where Γ is a cyclic group, these conditions do exclude existence in specific cases. On the other hand we produce several constructions for a wide range of admissible values, in particular for every admissible value of k when v is odd and Γ is an arbitrary group of odd order possessing a subgroup of order gcd(k,v).

Bonisoli, Arrigo; Bonvicini, Simona; Rinaldi, Gloria ( 2013 ) - A hierarchy of balanced graph-designs - QUADERNI DI MATEMATICA - n. volume 28 - pp. da 151 a 164 [Articolo in rivista (262) - Articolo su rivista]
Abstract

Decompositions of the complete graph K_v into subgraphs, all of which are isomorphic to some given non-regular graph G are considered. The decompositions are required to have the additional property that each vertex occurs a constant number of times as a vertex of given degree in the subgraphs of the decomposition. These decompositions are said to be degree-balanced G-designs. General properties of degree-balanced G-designs are studied and the spectrum of degree-balanced G-designs is determined when G is a bowtie. Moreover, for each v in this spectrum, there exists a bowtie design on v vertices which is not degree-balanced.

Bonvicini, Simona; Mazzuoccolo, Giuseppe ( 2013 ) - Covering cubic graphs with matchings of large size - TEH AUSTRALASIAN JOURNAL OF COMBINATORICS - n. volume 56 - pp. da 245 a 255 ISSN: 1034-4942 [Articolo in rivista (262) - Articolo su rivista]
Abstract

Let 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.

Bonvicini, Simona ( 2013 ) - Degree- and orbit-balanced Γ-designs when Γ has five vertices - JOURNAL OF COMBINATORIAL DESIGNS - n. volume 21 - pp. da 359 a 389 ISSN: 1063-8539 [Articolo in rivista (262) - Articolo su rivista]
Abstract

A Γ-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).

Bonvicini, Simona; Pisanski, Tomaž ( 2013 ) - Hamiltonian cycles in I–graphs - Combinatorics 2012 - Elsevier Amsterdam NLD) - ELECTRONIC NOTES IN DISCRETE MATHEMATICS - n. volume 40 - pp. da 43 a 47 ISSN: 1571-0653 [Abstract in rivista (266) - Abstract in Rivista]
Abstract

The I-graphs generalize the family of generalized Petersen graphs. We show that a connected I-graph which is not a generalized Petersen graph is Hamiltonian.

Bonvicini, Simona; M., Buratti; Rinaldi, Gloria; T., Traetta ( 2012 ) - Some progress on the existence of 1-rotational Steiner Triple Systems - DESIGNS, CODES AND CRYPTOGRAPHY - n. volume 62 - pp. da 63 a 78 ISSN: 0925-1022 [Articolo in rivista (262) - Articolo su rivista]
Abstract

A Steiner Triple System of order v (briefly STS(v)) is 1-rotational under G if it admits G as an automorphism group acting sharply transitively on all but one point.The spectrum of values of v for which there exists a1-rotational STS(v) under a cyclic, an abelian, or a generalized quaternion group, has beenestablished in 1981 (phelps and Rosa), in 2001 (Buratti) and in 2008 (Mishima), respectively.Nevertheless, the spectrum of values of v for which there exists a1-rotational STS(v) under an arbitrary group has not been completely determined yet.This paper is a considerable step forward to the solution of this problem.In fact, we leave as uncertain cases only those for which we have v = (p^3-p)n + 1 = 1 (mod 96)with p a prime, n =1,2,3 mod 4, and the odd part of (p^3-p)n that is square-free and without prime factors congruent to 1 mod 6.

Bonvicini, Simona; Mazzuoccolo, Giuseppe ( 2011 ) - Perfect one-factorizations in generalized Petersen graphs - ARS COMBINATORIA - n. volume 99 - pp. da 33 a 43 ISSN: 0381-7032 [Articolo in rivista (262) - Articolo su rivista]
Abstract

A perfectly one-factorable (P1F) regular graph G is a graph admitting a partition of the edge-set into one-factors such that the union of any two of them is a Hamiltonian cycle. We consider cubic graphs. The existence of a P1F cubic graph is guaranteed for each admissible value of the number of vertices. We give conditions for determining P1F graphs within a subfamily of generalized Petersen graphs.

Bonvicini, Simona; Mazzuoccolo, Giuseppe ( 2010 ) - Abelian 1-factorizations in infinite graphs - EUROPEAN JOURNAL OF COMBINATORICS - n. volume 7 - pp. da 1847 a 1852 ISSN: 0195-6698 [Articolo in rivista (262) - Articolo su rivista]
Abstract

For each finitely generated abelian group G, we construct a 1-factorization of the countable complete graph admitting G as an automorphism group acting sharply transitively on vertices.

Bonvicini, Simona; Zanella, Corrado ( 2010 ) - On generalized null polarities - DISCRETE MATHEMATICS - n. volume 310 - pp. da 3182 a 3187 ISSN: 0012-365X [Articolo in rivista (262) - Articolo su rivista]
Abstract

Assuming that a linear complex of planes without singular lines exists, the properties of the related generalized polarity are investigated.

Bonvicini, Simona; Ruini, Beatrice ( 2010 ) - Symmetric bowtie decompositions of the complete graph - ELECTRONIC JOURNAL OF COMBINATORICS - n. volume 17, R101 - pp. da 1 a 19 ISSN: 1077-8926 [Articolo in rivista (262) - Articolo su rivista]
Abstract

Given 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$v\equiv 1, 9\pmod{12}$, 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 $v\equiv 9\pmod{12}$ 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.

Bonvicini, Simona; G., Mazzuoccolo; Rinaldi, Gloria ( 2009 ) - On 2-factorizations of the complete graph: from the k-pyramidal to the universal property - JOURNAL OF COMBINATORIAL DESIGNS - n. volume 17 - pp. da 211 a 228 ISSN: 1063-8539 [Articolo in rivista (262) - Articolo su rivista]
Abstract

We consider 2-factorizations of complete graphs which possess an automorphism group fixing k\ge 0 vertices and acting sharply transitively on the others. We study the structures of such factorizations and consider the cases in which the group is either abelian or dihedral in somemore details. We prove that the class of 2-factorizations of complete graphs is universal. Namely each finite group is the full automorphism group of a 2-factorization of the class.

Bonvicini, Simona ( 2008 ) - Frattini-based starters in 2-groups - DISCRETE MATHEMATICS - n. volume 308 - pp. da 380 a 381 ISSN: 0012-365X [Articolo in rivista (262) - Articolo su rivista]
Abstract

Let 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.

Bonisoli, Arrigo; Bonvicini, Simona ( 2008 ) - Primitive one-factorizations and the geometry of mixed translations - DISCRETE MATHEMATICS - n. volume 308 - pp. da 726 a 733 ISSN: 0012-365X [Articolo in rivista (262) - Articolo su rivista]
Abstract

We construct an infinite family of one-factorizations of K_v admitting an automorphism group acting primitively on the set ofvertices but no such group acting doubly transitively. We also give examples of one-factorizations which are live, in the sense that every one-factor induces an automorphism, but do not coincide with the affine line parallelism of AG(n, 2). To this purpose we develop the notion of a “mixed translation” in AG(n, 2).

S. Bonvicini; G.Mazzuoccolo ( 2006 ) - A new description of perfecly one-factorable cubic graphs - Modena: Seminario Matematico e Fisico, Università di Modena ) - ATTI DEL SEMINARIO MATEMATICO E FISICO DEL'UNIVERSITÀ DI MODENA E REGGIO EMILIA - n. volume 54 - pp. da 167 a 173 ISSN: 1825-1269 [Articolo in rivista (262) - Articolo su rivista]
Abstract

A perfectly one-factorable (P1F) regular graph is a graph admitting a partition of the edge-set into one-factors such that the union of any two of them is a Hamiltonian cycle. The case of cubic graphs is treated. The existence of a P1F cubic graph is guaranteed for each admissible value of the number of vertices. A description of this class was obtained by Kotzigin 1962. It is the purpose of the present paper to produce an alternative proof of Kotzig's result.

S. Bonvicini; G. Mazzuoccolo ( 2006 ) - On perfectly one-factorable cubic graphs - Fifth Cracow Conference on Graph Theory USTRON '06 - Elsevier Amsterdam NLD) - ELECTRONIC NOTES IN DISCRETE MATHEMATICS - n. volume 24 - pp. da 47 a 51 ISSN: 1571-0653 [Abstract in rivista (266) - Abstract in Rivista]
Abstract

We study cubic graphs possessing a perfect one–factorization.

S. Bonvicini ( 2006 ) - Starters: Doubling Constructions - Institute of Combinatorics and its Applications:81 Walnut Street, Winnipeg Manitoba R3G 1N9 Canada:EMAIL: stanton@ccu.umanitoba.ca ) - BULLETIN OF THE INSTITUTE OF COMBINATORICS AND ITS APPLICATIONS - n. volume 46 - pp. da 88 a 98 ISSN: 1183-1278 [Articolo in rivista (262) - Articolo su rivista]
Abstract

Let 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.

S. Bonvicini ( 2006 ) - 1-fattorizzazioni e gruppi di automorfismi - BOLLETTINO DELL'UNIONE MATEMATICA ITALIANA. A - n. volume 9 - pp. da 211 a 214 ISSN: 0392-4033 [Articolo in rivista (262) - Articolo su rivista]
Abstract

All'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.

Bonvicini, Simona; Rinaldi, Gloria ( 2005 ) - Minkowski tangent-circle structures and key distribution patterns - University of Queensland:Mathematics Department, St. Lucia Queensland 4072 Australia:011 61 7 33652313, 011 61 7 33653277, 011 61 7 33653271, EMAIL: pa@maths.uq.edu.au, Fax: 011 61 7 33651477 ) - THE AUSTRALASIAN JOURNAL OF COMBINATORICS - n. volume 31 - pp. da 179 a 187 ISSN: 2202-3518 [Articolo in rivista (262) - Articolo su rivista]
Abstract

Key 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.