
Simona BONVICINI
Professore Associato Dipartimento di Scienze Fisiche, Informatiche e Matematiche sede exMatematica

Home 
Curriculum(pdf) 
Didattica 
Pubblicazioni
2022
 Even Cycle Decompositions of index 3 by a novel coloring technique
[Articolo su rivista]
Bonvicini, S.; Molinari, M. C.
abstract
An even cycle decomposition of an Eulerian graph is a partition of the edge set into even cycles. We color the even cycles so as two cycles sharing at least one vertex receive distinct colors. If k is the minimum number of required colors in such a coloring, then the even cycle decomposition has index k. We prove that the line graph of every bridgeless cubic graph of oddness 2 has an even cycle decomposition of index 3. The same property holds for the line graphs of some infinite families of class 2 cubic graphs with arbitrary large oddness. The construction of even cycle decompositions of index 3 in the line graph of a class 2 cubic graph is alternative to the constructions that are known in the literature; that one for the line graph of a cubic graph with arbitrary large oddness is also a new contribution to the more general problem on the existence of even cycle decompositions in the line graph of a bridgeless cubic graph. The constructions are obtained by applying a novel coloring technique on the edges of the line graph.
2021
 The first families of highly symmetric Kirkman Triple Systems whose orders fill a congruence class
[Articolo su rivista]
Bonvicini, S.; Buratti, M.; Garonzi, M.; Rinaldi, G.; Traetta, T.
abstract
Kirkman triple systems (KTSs) are among the most popular combinatorial designs and their existence has been settled a long time ago. Yet, in comparison with Steiner triple systems, little is known about their automorphism groups. In particular, there is no known congruence class representing the orders of a KTS with a number of automorphisms at least close to the number of points. We partially fill this gap by proving that whenever v≡ 39 (mod 72), or v≡ 4 e48 + 3 (mod 4 e96) and e≥ 0 , there exists a KTS on v points having at least v 3 automorphisms. This is only one of the consequences of an investigation on the KTSs with an automorphism group G acting sharply transitively on all but three points. Our methods are all constructive and yield KTSs which in many cases inherit some of the automorphisms of G, thus increasing the total number of symmetries. To obtain these results it was necessary to introduce new types of difference families (the doubly disjoint ones) and difference matrices (the splittable ones) which we believe are interesting by themselves.
2020
 A Möbiustype gluing technique for obtaining edgecritical graphs
[Articolo su rivista]
Bonvicini, Simona; Vietri, Andrea
abstract
Using a technique which is inspired by topology we construct original examples of 3 and 4edge critical graphs. The 3critical graphs cover all even orders starting from 26; the 4critical graphs cover all even orders starting from 20 and all the odd orders. In particular, the 3critical graphs are not isomorphic to the graphs provided by Goldberg for disproving the Critical Graph Conjecture. Using the same approach we also revisit the construction of some fundamental critical graphs, such as Goldberg's infinite family of 3critical graphs, Chetwynd's 4critical graph of order 16 and Fiol's 4critical graph of order 18.
2020
 On the minimum number of bondedge types and tile types: An approach by edgecolorings of graphs
[Articolo su rivista]
Bonvicini, S.; Ferrari, MARGHERITA MARIA
abstract
The purpose of this paper is twofold. On one hand, we want to describe from a new graph theory perspective the selfassembly of DNA structures with branched junction molecules having flexible arms. On the other hand, we employ edgecolorings and graph decompositions to study the wellknown problem of determining the minimum number of bondedge types and tile types, which are graph invariants appearing in this context. We provide a strategy that can be applied to arbitrary graphs for obtaining upper bounds for these graph invariants.
2018
 Indecomposable 1factorizations of the complete multigraph λK2n for every λ≤2n
[Articolo su rivista]
Rinaldi, Gloria; Bonvicini, Simona
abstract
A 1factorization of the complete multigraph λK2n is said to be indecomposable if it cannot be represented as the union of 1factorizations of λ0K2n and (λ  λ0)K2n, where λ0 < λ. It is said to be simple if no 1factor is repeated. For every n ≥ 9 and for every (n  2)/3 ≤ λ ≤ 2n, we construct an indecomposable 1factorization of λK2n, which is not simple. These 1factorizations provide simple and indecomposable 1factorizations 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 1factorization of λK2n, where 2n = pm + 1, λ = (pm  1)/2, p prime.
2018
 Octahedral, dicyclic and special linear solutions of some HamiltonWaterloo problems
[Articolo su rivista]
Bonvicini, Simona; Buratti, Marco
abstract
We give a sharplyvertextransitive solution of each of the nine HamiltonWaterloo problems left open by Danziger, Quattrocchi and Stevens.
2017
 A novel characterization of cubic Hamiltonian graphs via the associated quartic graphs
[Articolo su rivista]
Bonvicini, Simona; Pisanski, Tomaž
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 1factor contraction. This correspondence is most useful in the case when it induces a blue and red 2factorization of the associated quartic graph. We use this condition to characterize the Hamiltonian Igraphs, a further generalization of generalized Petersen graphs. The characterization of Hamiltonian Igraphs follows from the fact that one can choose a 1factor in any Igraph 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 Igraphs as a subfamily.
2017
 Even cycles and even 2factors in the line graph of a simple graph
[Articolo su rivista]
Bonisoli, Arrigo; Bonvicini, Simona
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 2factor whose connected components are cycles of even length (an even 2factor). 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 edgeset of L(G) can be partitioned into three 2regular subgraphs whose connected components are cycles of even length. The more general problem of the existence of even cycle decompositions of index m in 2dregular graphs is also addressed.
2017
 On the palette index of a graph: the case of trees
[Articolo su rivista]
Bonisoli, Arrigo; Bonvicini, Simona; Mazzuoccolo, Giuseppe
abstract
The palette of a vertex v of a graph G in a proper edgecoloring 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 edgecolorings of G. After reviewing some results on the palette index of regular graphs, we consider the problem of determining the palette index for nonregular 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.
2016
 Edgecolorings of 4regular graphs with the minimum number of palettes
[Articolo su rivista]
Bonvicini, Simona; Mazzuoccolo, G.
abstract
A proper edgecoloring of a graph G is an assignment of colors to the edges of G such that adjacent edges receive distinct
colors. A proper edgecoloring 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 edgecolorings of G? A complete answer is known for complete graphs and cubic graphs. We study in some detail the problem for 4regular graphs.
2014
 On the existence spectrum for sharply transitive Gdesigns, G a [k]matching
[Articolo su rivista]
Bonisoli, Arrigo; Bonvicini, Simona
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 noncyclic 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).
2013
 A hierarchy of balanced graphdesigns
[Articolo su rivista]
Bonisoli, Arrigo; Bonvicini, Simona; Rinaldi, Gloria
abstract
Decompositions of the complete graph K_v into subgraphs, all of which are isomorphic to some given nonregular 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 degreebalanced Gdesigns. General properties of degreebalanced Gdesigns are studied and the spectrum of degreebalanced Gdesigns 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 degreebalanced.
2013
 Covering cubic graphs with matchings of large size
[Articolo su rivista]
Bonvicini, Simona; Mazzuoccolo, Giuseppe
abstract
Let m be a positive integer and let G be a cubic graph of order 2n. We consider the problem of covering the edgeset 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 = n1. We show how this parameter can be large for cubic graphs with low connectivity and we furnish some evidence that each cyclically 4connected cubic graph of order 2n has excessive [n1]index at most 4. Finally, we discuss the relation between excessive [n1]index and some other graph parameters such as oddness and circumference.
2013
 Degree and orbitbalanced Γdesigns when Γ has five vertices
[Articolo su rivista]
Bonvicini, Simona
abstract
A Γdesign of the complete graph Kv is a set D of subgraphs isomorphic to Γ (blocks) whose edgesets partition the edgeset 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 orbitbalanced, or strongly balanced, if the number of blocks containing x as a vertex of a vertexorbit 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 vertexorbit A of Γ. We say that D is degreebalanced 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 orbitbalanced Γdesign is also degreebalanced; a degreebalanced Γdesign is also balanced. The converse is not always true. We study the spectrum for orbitbalanced, degreebalanced, 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, degreebalanced) Γdesigns of Kv which are not degreebalanced (respectively, not orbitbalanced).
2013
 Hamiltonian cycles in I–graphs
[Articolo su rivista]
Bonvicini, Simona; Pisanski, Tomaž
abstract
The Igraphs generalize the family of generalized Petersen graphs. We show that a connected Igraph which is not a generalized Petersen graph is Hamiltonian.
2012
 Some progress on the existence of 1rotational Steiner Triple Systems
[Articolo su rivista]
Bonvicini, Simona; M., Buratti; Rinaldi, Gloria; T., Traetta
abstract
A Steiner Triple System of order v (briefly STS(v)) is 1rotational 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 a1rotational 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 a1rotational 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^3p)n + 1 = 1 (mod 96)with p a prime, n =1,2,3 mod 4, and the odd part of (p^3p)n that is squarefree and without prime factors congruent to 1 mod 6.
2011
 Perfect onefactorizations in generalized Petersen graphs
[Articolo su rivista]
Bonvicini, Simona; Mazzuoccolo, Giuseppe
abstract
A perfectly onefactorable (P1F) regular graph G is a graph admitting a partition of the edgeset into onefactors 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.
2010
 Abelian 1factorizations in infinite graphs
[Articolo su rivista]
Bonvicini, Simona; Mazzuoccolo, Giuseppe
abstract
For each finitely generated abelian group G, we construct a 1factorization of the countable complete graph admitting G as an automorphism group acting sharply transitively on vertices.
2010
 On generalized null polarities
[Articolo su rivista]
Bonvicini, Simona; Zanella, Corrado
abstract
Assuming that a linear complex of planes without singular lines exists, the properties of the related generalized polarity are investigated.
2010
 Symmetric bowtie decompositions of the complete graph
[Articolo su rivista]
Bonvicini, Simona; Ruini, Beatrice
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 nonexistence 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 havenonexistence 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 1rotational,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 Ginvariant bowtie decomposition is excludedwhen $v\equiv 9\pmod{12}$ and is equivalent to the existence ofa Ginvariant 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 1rotational. If,instead, G is assumed to act primitively then existence canbe excluded when v is a prime power satisfying someadditional arithmetic constraint.
2009
 On 2factorizations of the complete graph: from the kpyramidal to the universal property
[Articolo su rivista]
Bonvicini, Simona; G., Mazzuoccolo; Rinaldi, Gloria
abstract
We consider 2factorizations 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 2factorizations of complete graphs is universal. Namely each finite group is the full automorphism group of a 2factorization of the class.
2008
 Frattinibased starters in 2groups
[Articolo su rivista]
Bonvicini, Simona
abstract
Let G be a group of order 2^t , with t >3. We prove a sufficient condition for the existence of a onefactorization of a completegraph, admitting G as an automorphism group acting sharply transitively on the vertexset.
2008
 Primitive onefactorizations and the geometry of mixed translations
[Articolo su rivista]
Bonisoli, Arrigo; Bonvicini, Simona
abstract
We construct an infinite family of onefactorizations 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 onefactorizations which are live, in the sense that every onefactor 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).
2006
 A new description of perfecly onefactorable cubic graphs
[Articolo su rivista]
Bonvicini, Simona; G., Mazzuoccolo
abstract
A perfectly onefactorable (P1F) regular graph is a graph admitting a partition of the edgeset into onefactors 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.
2006
 On perfectly onefactorable cubic graphs
[Articolo su rivista]
Bonvicini, Simona; Mazzuoccolo, Giuseppe
abstract
We study cubic graphs possessing a perfect one–factorization.
2006
 Starters: Doubling Constructions
[Articolo su rivista]
Bonvicini, Simona
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 onefactorization F and admits G as an automorphism group acting sharply transitively on vertices.
2006
 1fattorizzazioni e gruppi di automorfismi
[Articolo su rivista]
Bonvicini, Simona
abstract
All'aumentare del numero dei vertici del grafo completo, il numero delle 1fattorizzazioni diventa enorme. Dare una classificazione completa delle 1fattorizzazioni risulta molto difficile. Classificazioni parziali, ossia classificazioni basate su determinate proprietà, risultano più facili. In questa nota vengono prese in considerazione 1fattorizzazioni con proprietà di simmetria, vale a dire 1fattorizzazioni con un gruppo di automorfismi non banale.
2005
 Minkowski tangentcircle structures and key distribution patterns
[Articolo su rivista]
Bonvicini, Simona; Rinaldi, Gloria
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 tangentcircle structures and show how to construct key distribution patterns from them.