David Cariolaro's papers

Below we list David Cariolaro's papers and unpublished dissertations. For most of the papers we give Cariolaro's Abstract and, in one case, his Introduction. We have slightly modified some of the technicalities in some of the abstracts and omitted abstracts which are highly technical. All twenty-six items have David Cariolaro as an author and we have listed any co-authors.

Un'estensione del concetto di integrale sfumato rispetto a misure compositive (Tesi di Laurea, Universitá di Pavia, 1995).
(with Carlo Bertoluzza) On the measure of a fuzzy set based on continuous t-conorms, Fuzzy Sets and Systems 88 (1997), 355-36.

Comment:

Received October 1995; revised February 1996.

Abstract:

The original aim of this research was the introduction of a compositive measure of information on a class (an algebra) of fuzzy subsets of an universe W. However, there is a bijection between the class of compositive informations and the class of decomposable measures. Therefore, we restated our problem as the one of the construction of a decomposable measure over the space $(W, A^{*})$ , starting from a crisp measure defined on $(W, A)$ . Here $A$ and $A^{*}$ are suitable algebras of, respectively, crisp and fuzzy subsets of $W$ (the measurable ones). This problem has been analyzed by many authors in some special cases; in particular if the crisp measure is a possibility (Sugeno) or an archimedean decomposable measure. Here we present an approach which permits us to construct such a fuzzy measure in the case where the crisp one has an arbitrary continuous composition law. The main results and the detailed proofs are contained in [Cariolaro's Tesi di Laurea]. Finally, the original information problem can be solved by a symmetrization of the obtained results.
On the Ramsey number $R(3,6)$ , Research Report R-99-2012 (Aalborg University, Denmark, 1999).

Comment:

The results in this report were published in a paper by Cariolaro in 2007.
(with Anthony J W Hilton) Class 1 graphs associated with regular graphs of high degree, Congressus Numerantium 159 (2002), 133-142.
(with Gianfranco Cariolaro) Colouring the petals of a graph, Electron. J. Combin. 10 (2003), Research Paper 6, 11 pages (electronic).

Comment:

Gianfranco Cariolaro is David Cariolaro's father.

Abstract:

A petal graph is a connected graph $G$ with maximum degree three, minimum degree two, and such that the set of vertices of degree three induces a 2-regular graph and the set of vertices of degree two induces an empty graph. We prove here that, with the single exception of the graph obtained from the Petersen graph by deleting one vertex, all petal graphs are Class 1. This settles a particular case of a conjecture of Hilton and Zhao.
On fans in multigraphs, J. Graph Theory 51 (4) (2006), 301-318.

Comment:

This paper was submitted in May 2004 while Cariolaro was still at Reading. By the time it was published he was in Taiwan.

Abstract:

This paper has been inspired by the recent brilliant article [Short proofs of classical theorems (2003)] by Prof J A Bondy. The author thanks Prof A J W Hilton for his useful remarks that significantly helped him to improve the clarity of the paper. While this paper was been written, Prof L D Andersen informed the author (supplying abundant evidence in support of his claim), that in [Edge-colourings of graphs (Andersen's Ph.D. Thesis, 1975)] he had had the idea of associating a directed walk to a fan in a multigraph, although he did not develop this idea thoroughly as we have done here and in [Cariolaro's Ph.D. thesis].
On the Ramsey number $R(3,6)$ , Australas. J. Combin. 37 (2007), 301-304.

Comment:

Paper based on Cariolaro's research in Aalborg University and contained in Research Report R-99-2012 (Aalborg University, Denmark, 1999).
(with Arrigo Bonisoli ) Excessive factorizations of regular graphs, in Graph theory in Paris (Trends Math., Birkhäuser, Basel, 2007), 73-84.

Abstract:

An excessive factorization of a graph $G$ is a minimum set $F$ of 1-factors of $G$ whose union is $E(G)$ . In this paper we study excessive factorizations of regular graphs. We introduce two graph parameters related to excessive factorizations and show that their computation is NP-hard. We pose a number of questions regarding these parameters. We show that the size of an excessive factorization of a regular graph can exceed the degree of the graph by an arbitrarily large quantity. We conclude with a conjecture on the excessive factorizations of r-graphs.
1-factorization of regular graphs by colour exchange, J. Lond. Math. Soc. (2) 77 (2) (2008), 387-404.

Abstract:

We present a new general theory that deals with the problem of determining a 1-factorization of a graph using only the elementary technique of colour exchange. Our work is inspired by an old question of Vizing, who in [Cybernetics 3 (1965) 32-41] asked whether an optimal edge colouring of any multigraph $G$ can always be obtained from an arbitrary edge colouring of $G$ by repeatedly exchanging colours along bicoloured chains and suppressing empty colour classes. We conjecture that the answer to Vizing's question is affirmative. We apply our theory to the class of regular graphs of even order at most 10, proving the validity of this conjecture for this class of graphs. This yields an algorithm for finding a 1-factorization of any 1-factorizable graph of order at most 10. We also formulate two (stronger) conjectures and prove that they hold for the same class of graphs. Our method can be extended to graphs of larger order and to non-regular graphs or multigraphs.
(with Hung-Lin Fu) On minimum sets of 1-factors covering a complete multipartite graph, J. Graph Theory 58 (3) (2008), 239-250.

Abstract:

We determine necessary and sufficient conditions for a complete multipartite graph to admit a set of 1-factors whose union is the whole graph and, when these conditions are satisfied, we determine the minimum size of such a set.
An adjacency lemma for critical multigraphs, Discrete Math. 308 (20) (2008), 4791-4795.

Abstract:

In edge colouring it is often useful to have information about the degree distribution of the neighbours of a given vertex. For example, the well-known Vizing's Adjacency Lemma provides a useful lower bound on the number of vertices of maximum degree adjacent to a given one in a critical graph. We consider an extension of this problem, where we seek information on vertices at distance two from a given vertex in a critical graph. We extend and, simultaneously, generalize to multigraphs two results proved, respectively, by Zhang [Every planar graph with maximum degree seven is Class 1 (2000)] and Sanders and Zhao [Planar graphs of maximum degree seven are Class 1 (2001)].
The fire index, Graph Theory Notes N. Y. 54 (2008), 6-11.

Comment:

Cariolaro writes "Dedicated to the memory of the 343 Firefighters who lost their lives in New York City on the 11th of September 2001". Note that Cariolaro spent a year undertaking military service as a firefighter in Padua.

Abstract:

We introduce a new graph parameter $f^{*}(G)$ , which may be defined as the largest order of all the fan digraphs associated to the edge-deleted colourings of the critical subgraphs of $G$ . We then show its importance in edge colouring. In particular, we give generalizations of Vizing's Theorem, Shannon's Theorem and Vizing's Adjacency Lemma, and an extension to multigraphs of the simple graph version of Vizing's Theorem which is obtained by proving that the chromatic index of an arbitrary multigraph must assume one of only two possible values. We call f* the Fire Index.
(with Ko-Wei Lih) The edge choosability of the tetrahedron, The Mathematical Gazette 92 (November 2008), 543-546.

Abstract:

We consider a list-colouring type of problem on the edges of the graph $K_{4}$ , which is the skeleton of a tetrahedron and consists of four vertices, each pair of which is joined by one edge. Suppose that each edge of this graph is assigned a list of three distinct colours, where the list assigned to each edge may be different from the lists assigned to the other edges. The question which we address is the following: is it possible to choose one colour for each edge from the edge's list in such a way that the resulting colouring of the edges of $K_{4}$ has the property that any two edges which are adjacent (i.e. have a common endpoint) receive a different colour? We shall see that the answer to this question is always positive, no matter which lists are assigned to the edges of $K_{4}$ . The problem is a special case of a long standing conjecture in graph theory, known as the List-Colouring Conjecture, first posed by Vizing in 1976.
(with Hung-Lin Fu) Excessive near 1-factorizations, Discrete Math. 309 (14) (2009), 4690-4696.

Abstract:

We begin the study of sets of near 1-factors of graphs $G$ of odd order whose union contains all the edges of G and determine, for a few classes of graphs, the minimum number of near 1-factors in such sets.
(with Anthony J W Hilton) An application of Tutte's theorem to 1-factorization of regular graphs of high degree, Discrete Math. 309 (14) (2009), 4736-4745.
A theorem in edge colouring, Discrete Math. 309 (12) (2009), 4208-4209.

Abstract:

We prove the following theorem: if $G$ is an edge-chromatic critical multigraph with more than 3 vertices, and if $x, y$ are two adjacent vertices of $G$ , the edge-chromatic number of $G$ does not change if we add an extra edge joining $x$ and $y$ .
(with Hung-Lin Fu) The excessive [3]-index of all graphs, Electron. J. Combin. 16 (1) (2009), Research Paper 124, 17 pages.
(with Hung-Lin Fu) Covering graphs with matchings of fixed size, Discrete Math. 310 (2) (2010), 276-287.

Abstract:

Let m be a positive integer and let $G$ be a graph. We consider the question: can the edge set $E(G)$ of $G$ be expressed as the union of a set $M$ of matchings of $G$ each of which has size exactly $m$ ? If this happens, we say that $G$ is $[m]$ -coverable and we call $M$ an $[m]$ -covering of $G$ . It is interesting to consider minimum $[m]$ -coverings, i.e. [m]-coverings containing as few matchings as possible. Such $[m]$ -coverings will be called excessive $[m]$ -factorizations. The number of matchings in an excessive [m]-factorization is a graph parameter which will be called the excessive $[m]$ -index. In this paper we begin the study of this new parameter as well as of a number of other related graph parameters.
Some consequences of a theorem on fans, Taiwanese J. Math. 14 (1) (2010), 35-45.

Abstract:

Using a fundamental identity concerning fans called the 'Fan Theorem' we give new proofs of classical edge colouring theorems.
(with Romeo Rizzi) Excessive factorizations of bipartite multigraphs, Discrete Appl. Math. 158 (16) (2010), 1760-1766.
Some remarks on a paper of Chetwynd and Hilton on critical star multigraphs, J. Combin. Math. Combin. Comput. 77 (2011), 161-172.

Abstract:

In [Critical star multigraphs (1986)] A G Chetwynd and A J W Hilton started the investigations of the edge-chromatic properties of a particular class of multigraphs, which they called star multigraphs. A star multigraph is a multigraph such that there exists a vertex $v^{*}$ that is incident with each multiple edge. Star multigraphs turn out to be useful tools in the study of the chromatic index of simple graphs. The main goal of this paper is to provide shorter and simpler proofs of all the main theorems contained in the above mentioned paper. Most simplifications are achieved by means of a formula for the chromatic index recently obtained by the author and by a careful use of arguments involving fans.
(with S Akbari, M Chavooshi, M Ghanbari and S Zare) Some criteria for a graph to be Class 1, Discrete Math. 312 (17) (2012), 2593-2598.
(with Zhaiming Shen, Yi Zhang) Group Testing with Pools of Fixed Size, arXiv:1407.3631 (15 July 2014).

Comment:

The paper had a note attached which reads: "Unfortunately, Professor David Cariolaro passed away before the completion of this paper."

Abstract:

In the classical combinatorial (adaptive) group testing problem, one is given two integers $d$ and $n$ , where $0 ≤ d ≤ n$ , and a population of $n$ items, exactly $d$ of which are known to be defective. The question is to devise an optimal sequential algorithm that, at each step, tests a subset of the population and determines whether such subset is contaminated (i.e. contains defective items) or otherwise. The problem is solved only when the d defective items are identified. The minimum number of steps that an optimal sequential algorithm takes in general (i.e. in the worst case) to solve the problem is denoted by $M(d, n)$ . The computation of $M(d, n)$ appears to be very difficult and a general formula is known only for $d = 1$ . We consider here a variant of the original problem, where the size of the subsets to be tested is restricted to be a fixed positive integer $k$ . The corresponding minimum number of tests by a sequential optimal algorithm is denoted by $M[k](d, n)$ . In this paper we start the investigation of the function $M[k](d, n)$ .
(with Gianfranco Cariolaro, U Schauz and Xu Sun) The list-chromatic index of $K_{6}$ , Discrete Math. 322 (2014), 15-18.

Comment:

Gianfranco Cariolaro is David Cariolaro's father.

Abstract:

We prove that the list-chromatic index and paintability index of $K_{6}$ is 5. That ... was a still open special case of the List Colouring Conjecture. Our proof demonstrates how colourability problems can numerically be approached by the use of computer algebra systems and the Combinatorial Nullstellensatz.
(with Romeo Rizzi) Polynomial time complexity of edge colouring graphs with bounded colour classes, Algorithmica 69 (3) (2014), 494-500.

Abstract:

We show that the following fundamental edge-colouring problem can be solved in polynomial time for any given constant $B$ : given a simple graph $G$ , find an edge-colouring of $G$ where each colour is assigned to at most $B$ edges and which, subject to this condition, has the fewest number of colour classes.
(with Giuseppe Mazzuoccolo) Excessive $[l, m]$ -factorizations, Discrete Math. 338 (11) (2015), 1917-1927.

Comment:

The paper ends with the following note. "Giuseppe Mazzuoccolo dedicates this paper to the memory of his friend and coauthor David Cariolaro, who passed away in very sad circumstances during the revision process of this paper, in the hope that his mathematics will be continued in the future."

Introduction:

The classical concept of graph factorization as the decomposition of the edge set of a graph into (pairwise isomorphic) factors is a very general concept which has received a substantial amount of attention in the literature. One limitation of the use of such concept is that it is normally applicable only to specific classes of graphs, such as complete graphs, or k-factorizable graphs, etc. In 2004 one extension of the concept of 1-factorization, called excessive factorization, which is applicable to a wider class of graphs, has been proposed [Cariolaro's Ph.D. thesis] (see also [A Bonisoli and D Cariolaro, Excessive factorizations of regular graphs (2007)]). Informally speaking, an excessive factorization of a graph $G$ is a minimum set of (not necessarily edge-disjoint) 1-factors of G whose union is the edge set of $G$ . Thus, in order for a graph to admit an excessive factorization, it is not necessary that it is 1-factorizable (or even regular), and hence, using this new concept, one can develop and apply the results of the corresponding theory to a much wider class of graphs. Of course one may observe that there are limitations also in the concept of excessive factorization, in what it applies only to graphs having 1-factors and, more precisely, having 1-factors containing any prescribed edge of the graph. It is therefore desirable to study extensions of this concept by replacing the term "1-factor" by something more general. However, if we replace the term "1-factor" by "arbitrary matching" what we obtain is essentially the concept of edge colouring, which has been studied since the nineteenth century and is therefore not a new concept. An intermediate possibility is to replace the term "1-factor" by "matching of fixed size m", and this idea was pursued by Cariolaro and Fu in [Covering graphs with matchings of fixed size (2010)], where the corresponding concept was called "excessive [m]-factorization".

Last Updated July 2015