Nuova ricerca

Simona BONVICINI

Professore Associato
Dipartimento di Scienze Fisiche, Informatiche e Matematiche sede ex-Matematica

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öbius-type gluing technique for obtaining edge-critical graphs [Articolo su rivista]
Bonvicini, Simona; Vietri, Andrea
abstract

Using a technique which is inspired by topology we construct original examples of 3- and 4-edge critical graphs. The 3-critical graphs cover all even orders starting from 26; the 4-critical graphs cover all even orders starting from 20 and all the odd orders. In particular, the 3-critical 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 3-critical graphs, Chetwynd's 4-critical graph of order 16 and Fiol's 4-critical graph of order 18.

2020 - On the minimum number of bond-edge types and tile types: An approach by edge-colorings 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 self-assembly of DNA structures with branched junction molecules having flexible arms. On the other hand, we employ edge-colorings and graph decompositions to study the well-known problem of determining the minimum number of bond-edge 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 1-factorizations of the complete multigraph λK2n for every λ≤2n [Articolo su rivista]
Rinaldi, Gloria; Bonvicini, Simona
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.

2018 - Octahedral, dicyclic and special linear solutions of some Hamilton-Waterloo problems [Articolo su rivista]
Bonvicini, Simona; Buratti, Marco
abstract

We give a sharply-vertex-transitive solution of each of the nine Hamilton-Waterloo 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 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.

2017 - Even cycles and even 2-factors 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 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.

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

2016 - Edge-colorings of 4-regular graphs with the minimum number of palettes [Articolo su rivista]
Bonvicini, Simona; Mazzuoccolo, G.
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.

2014 - On the existence spectrum for sharply transitive G-designs, 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 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).

2013 - A hierarchy of balanced graph-designs [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 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.

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

2013 - Degree- and orbit-balanced Γ-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 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).

2013 - Hamiltonian cycles in I–graphs [Articolo su rivista]
Bonvicini, Simona; Pisanski, Tomaž
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.

2012 - Some progress on the existence of 1-rotational 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 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.

2011 - Perfect one-factorizations in generalized Petersen graphs [Articolo su rivista]
Bonvicini, Simona; Mazzuoccolo, Giuseppe
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.

2010 - Abelian 1-factorizations in infinite graphs [Articolo su rivista]
Bonvicini, Simona; Mazzuoccolo, Giuseppe
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.

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

2009 - On 2-factorizations of the complete graph: from the k-pyramidal to the universal property [Articolo su rivista]
Bonvicini, Simona; G., Mazzuoccolo; Rinaldi, Gloria
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.

2008 - Frattini-based starters in 2-groups [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 one-factorization of a completegraph, admitting G as an automorphism group acting sharply transitively on the vertex-set.

2008 - Primitive one-factorizations and the geometry of mixed translations [Articolo su rivista]
Bonisoli, Arrigo; Bonvicini, Simona
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).

2006 - 1-fattorizzazioni e gruppi di automorfismi [Articolo su rivista]
Bonvicini, Simona
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.

2006 - A new description of perfecly one-factorable cubic graphs [Articolo su rivista]
Bonvicini, Simona; G., Mazzuoccolo
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.

2006 - On perfectly one-factorable 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 one-factorization F and admits G as an automorphism group acting sharply transitively on vertices.

2005 - Minkowski tangent-circle 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 tangent-circle structures and show how to construct key distribution patterns from them.