BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Josef Lauri appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
This note is a continuation of postgraduate thesis research carried out by the first author under the supervision of the second author at the University of Malta. In that research we took a look at several results relating Schur rings to sufficient conditions for GRRs and then applied those results to produce numerical methods for constructing trivalent GRRs for dihedral groups very quickly.
In this paper we shall be looking at several results relating Schur rings to sufficient conditions for a graph to be a graphical regular representation (GRR) of a finite group, and then applying these specifically in the case of certain subfamilies of dihedral groups. Numerical methods are given for constructing trivalent GRRs for these dihedral groups very quickly.
Let $G$ be a prolific graph, that is a finite connected simple graph which is not isomorphic to a cycle nor a path nor the star graph $K_{1,3}$. The line-graph of $G$, denoted by $L(G)$, is defined by having its vertex-set equal to the edge-set of $G$ and two vertices of $L(G)$ are adjacent if the corresponding edges are adjacent in $G$. For a positive integer $k$, the iterated line-graph $L^k(G)$ is defined recursively by $L^k(G)=L(L^{k-1}(G))$. We consider fifteen graph parameters and study their behaviour when the operation of taking the line-graph is iterated. We shall first show that all of these parameters are unbounded. This idea is motivated by a well-known result of van Rooij and Wilf that says that the number of vertices is unbounded if and only if the graph is prolific. We then study of the value of $k(P,{\mathcal F})$, which is the index of a family of prolific graphs with regards to a given graph parameter $P(G)$. For a given parameter $P(G)$, the index of $G$ is denoted by $ind(P,G) = \min \{ r : P(G) < P(L^r(G) \}$. Now for a family $\mathcal F$ of prolific graphs, the index of the family is $k(P,\mathcal{F}) = \max \{ ind(P,G) : G \in \mathcal F\}$. The problem of determining the index of a parameter over the family of prolific graphs is motivated by a result of Chartrand who showed that it could require $k=|V(G)|-3$ iterations for $L^k(G)$ to have a hamiltonian cycle. For twelve of the parameters considered, we exactly determine $k(P,\mathcal F)$ where $\mathcal F$ is the family of all prolific graphs, and for some parameters we also characterize the class of prolific graphs realizing the extremal value $k(P,\mathcal F$). Interesting open problems remain, in particular completing the determination of $k(P,\mathcal F)$ for the three parameters: the independence number, independent domination number and domination number.
We consider the following feasibility problem: given an integer $n \geq 1$ and an integer $m$ such that $0 \leq m \leq \binom{n}{2}$, does there exist a line graph $L = L(G)$ with exactly $n$ vertices and $m$ edges ? We say that a pair $(n,m)$ is non-feasible if there exists no line graph $L(G)$ on $n$ vertices and $m$ edges, otherwise we say $(n,m)$ is a feasible pair. Our main result shows that for fixed $n\geq 5$, the values of $m$ for which $(n, m)$ is a non-feasible pair, form disjoint blocks of consecutive integers which we completely determine. On the other hand we prove, among other things, that for the more general family of claw-free graphs (with no induced $K_{1,3}$-free subgraph), all $(n,m)$-pairs in the range $0 \leq m \leq \binom{n}{2}$ are feasible pairs.
In Ramsey theory for graphs we are given a graph $G$ and we are required to find the least $n_0$ such that, for any $n\geq n_0$, any red/blue colouring of the edges of $K_n$ gives a subgraph $G$ all of whose edges are blue or all are red. Here we shall be requiring that, for any red/blue colouring of the edges of $K_n$, there must be a copy of $G$ such that its edges are partitioned equally as red or blue (or the sizes of the colour classes differs by one in the case when $G$ has an odd number of edges). This introduces the notion of balanceable graphs and the balance number of $G$ which, if it exists, is the minimum integer bal$(n, G)$ such that, for any red/blue colouring of $E(K_n)$ with more than bal$(n, G)$ edges of either colour, $K_n$ will contain a balanced coloured copy of $G$ as described above. This parameter was introduced by Caro, Hansberg and Montejano in \cite{2018arXivCHM}. There, the authors also introduce the strong balance number sbal$(n,G)$ and the more general omnitonal number ot$(n, G)$ which requires copies of $G$ containing a complete distribution of the number of red and blue edges over $E(G)$. In this paper we shall catalogue bal$(n, G)$, sbal$(n, G)$ and ot$(n,G)$ for all graphs $G$ on at most four edges. We shall be using some of the key results of Caro et al, which we here reproduce in full, as well as some new results which we prove here. For example, we shall prove that the union of two bipartite graphs with the same number of edges is always balanceable.
We consider $2$-colourings $f : E(G) \rightarrow \{ -1 ,1 \}$ of the edges of a graph $G$ with colours $-1$ and $1$ in $\mathbb{Z}$. A subgraph $H$ of $G$ is said to be a zero-sum subgraph of $G$ under $f$ if $f(H) := \sum_{e\in E(H)} f(e) =0$. We study the following type of questions, in several cases obtaining best possible results: Under which conditions on $|f(G)|$ can we guarantee the existence of a zero-sum spanning tree of $G$? The types of $G$ we consider are complete graphs, $K_3$-free graphs, $d$-trees, and maximal planar graphs. We also answer the question of when any such colouring contains a zero-sum spanning path or a zero-sum spanning tree of diameter at most $3$, showing in passing that the diameter-$3$ condition is best possible. Finally, we give, for $G = K_n$, a sharp bound on $|f(K_n)|$ by which an interesting zero-sum connectivity property is forced, namely that any two vertices are joined by a zero-sum path of length at most $4$. One feature of this paper is the proof of an Interpolation Lemma leading to a Master Theorem from which many of the above results follow and which can be of independent interest.
A perfect forest is a spanning forest of a connected graph $G$, all of whose components are induced subgraphs of $G$ and such that all vertices have odd degree in the forest. A perfect forest generalised a perfect matching since, in a matching, all components are trees on one edge. Scott first proved the Perfect Forest Theorem, namely, that every connected graph of even order has a perfect forest. Gutin then gave another proof using linear algebra. We give here two very short proofs of the Perfect Forest Theorem which use only elementary notions from graph theory. Both our proofs yield polynomial-time algorithms for finding a perfect forest in a connected graph of even order.
We look at colourings of $r$-uniform hypergraphs, focusing our attention on unique colourability and gaps in the chromatic spectrum. The pattern of an edge $E$ in an $r$-uniform hypergraph $H$ whose vertices are coloured is the partition of $r$ induced by the colour classes of the vertices in $E$. Let $Q$ be a set of partitions of $r$. A $Q$-colouring of $H$ is a colouring of its vertices such that only patterns appearing in $Q$ are allowed. We first show that many known hypergraph colouring problems, including Ramsey theory, can be stated in the language of $Q$-colourings. Then, using as our main tools the notions of $Q$-colourings and $Σ$-hypergraphs, we define and prove a result on tight colourings, which is a strengthening of the notion of unique colourability. $Σ$-hypergraphs are a natural generalisation of $σ$-hypergraphs introduced by the first two authors in an earlier paper. We also show that there exist $Σ$-hypergraphs with arbitrarily large $Q$-chromatic number and chromatic number but with bounded clique number. Dvorak et al. have characterised those $Q$ which can lead to a hypergraph with a gap in its $Q$-spectrum. We give a short direct proof of the necessity of their condition on $Q$. We also prove a partial converse for the special case of $Σ$-hypergraphs. Finally, we show that, for at least one family $Q$ which is known to yield hypergraphs with gaps, there exist no $Σ$-hypergraphs with gaps in their $Q$-spectrum.
We consider vertex colourings of $r$-uniform hypergraphs $H$ in the classical sense, that is such that no edge has all its vertices given the same colour, and $(2,2)$-colourings of $H$ in which the vertices in any edge are given exactly two colours. This is a special case of constrained colourings introduced by Bujtas and Tuza which, in turn, is a generalisation of Voloshin's colourings of mixed hypergraphs. We study, $χ(H)$, the classical chromatic number, and the $(2,2)$-spectrum of $H$, that is, the set of integers $k$ for which $H$ has a $(2,2)$-colouring using exactly $k$ colours. We present extensions of hypergraphs which preserve both the chromatic number and the $(2,2)$-spectrum and which, however often repeated, do not increase the clique number of $H$ by more than a fixed number. In particular, we present sparse $(2,2)$-colourable clique-free $σ$-hypergraphs having arbitrarily large chromatic number - these $r$-uniform hypergraphs were studied by the authors in earlier papers. We use these ideas to extend some known $3$-uniform hypergraphs which exhibit a $(2,2)$-spectrum with remarkable gaps. We believe that this work is the first to present an extension of hypergraphs which preserves both $χ(H)$ and the $(2,2)$-spectrum of $H$ simultaneously.
In this paper, we study the behaviour of TF-isomorphisms, a natural generalisation of isomorphisms. TF-isomorphisms allow us to simplify the approach to seemingly unrelated problems. In particular, we mention the Neighbourhood Reconstruction problem, the Matrix Symmetrization problem and Stability of Graphs. We start with a study of invariance under TF-isomorphisms. In particular, we show that alternating trails and incidence double covers are conserved by TF-isomorphisms, irrespective of whether they are TF-isomorphisms between graphs or digraphs. We then define an equivalence relation and subsequently relate its equivalence classes to the incidence double cover of a graph. By directing the edges of an incidence double cover from one colour class to the other and discarding isolated vertices we obtain an invariant under TF-isomorphisms which gathers a number of invariants. This can be used to study TF-orbitals, an analogous generalisation of the orbitals of a permutation group.
A constrained colouring or, more specifically, an $(α,β)$-colouring of a hypergraph $H$, is an assignment of colours to its vertices such that no edge of $H$ contains less than $α$ or more than $β$ vertices with different colours. This notion, introduced by B{ú}jtas and Tuza, generalises both classical hypergraph colourings and the more general Voloshin colourings of hypergraphs. In fact, for $r$-uniform hypergraphs, classical colourings correspond to $(2,r)$-colourings while an important instance of Voloshin colourings of $r$-uniform hypergraphs gives $(2, r-1)$-colourings. One intriguing aspect of all these colourings, not present in classical colourings, is that $H$ can have gaps in its $(α,β)$-spectrum, that is, for $k_1 < k_2 < k_3$, $H$ would be $(α,β)$-colourable using $k_1$ and using $k_3$ colours, but not using $k_2$ colours. In an earlier paper, the first two authors introduced, for $σ$ a partition of $r$, a very versatile type of $r$-uniform hypergraph which they called $σ$-hypergraphs. They showed that, by simple manipulation of the parameters of a $σ$-hypergraph $H$, one can obtain families of hypergraphs which have $(2,r-1)$-colourings exhibiting various interesting chromatic properties. They also showed that, if the smallest part of $σ$ is at least 2, then $H$ will never have a gap in its $(2,r-1)$-spectrum but, quite surprisingly, they found examples where gaps re-appear when $α=β=2$. In this paper we extend many of the results of the first two authors to more general $(α,β)$-colourings, and we study the phenomenon of the disappearanace and re-appearance of gaps and show that it is not just the behaviour of a particular example but we place it within the context of a more general study of constrained colourings of $σ$-hypergraphs.
We shall study degree-monotone paths in graphs, a problem inspired by the celebrated theorem of Erd{ő}s-Szekeres concerning the longest monotone subsequence of a given sequence of numbers. A path P in a graph G is said to be a degree monotone path if the sequence of degrees of the vertices in P in the order they appear in P is monotonic. In this paper we shall consider these three problem related to this parameter: 1. Find bounds on $mp(G)$ in terms of other parameters of $G$. 2. Study $f(n,k)$ defined to be the maximum number of edges in a graph on $n$ vertices with $mp(G) < k$. 3. Estimate the minimum and the maximum over all graph $G$ on $n$ vertices of $mp(G)+mp(\overline{G})$. For the first problem our main tool will be the Gallai-Roy Theorem on directed paths and chromatic number. We shall also consider in some detail maximal planar and maximal outerplanar graphs in order to investigate the sharpness of the bounds obtained. For the second problem we establish a close link between $f(n,k)$ and the classical Turan numbers. For the third problem we establish some Nordhaus-Gaddum type of inequalities. We conclude by indicating some open problems which our results point to.
A path $P$ in a graph $G$ is said to be a degree monotone path if the sequence of degrees of the vertices of $P$ in the order in which they appear on $P$ is monotonic. The length of the longest degree monotone path in $G$ is denoted by $mp(G)$. This parameter was first studied in an earlier paper by the authors where bounds in terms of other parameters of $G$ were obtained. In this paper we concentrate on the study of how $mp(G)$ changes under various operations on $G$. We first consider how $mp(G)$ changes when an edge is deleted, added, contracted or subdivided. We similarly consider the effects of adding or deleting a vertex. We sometimes restrict our attention to particular classes of graphs. Finally we study $mp(G \times H)$ in terms of $mp(G)$ and $mp(H)$ where $\times$ is either the Cartesian product or the join of two graphs. In all these cases we give bounds on the parameter $mp$ of the modified graph in terms of the original graph or graphs and we show that all the bounds are sharp.
Let $σ$ be a partition of the positive integer $r$. A $σ$-hypergraph $H=H(n,r,q|σ)$ is an $r$-uniform hypergraph on $nq$ vertices which are partitioned into $n$ classes $V_1, V_2, \ldots, V_n$ each containing $q$ vertices. An $r$-subset $K$ of vertices is an edge of the hypergraph if the partition of $r$ formed by the non-zero cardinalities $|K\cap V_i|, 1\leq i \leq n,$ is $σ$. In earlier works we have considered colourings of the vertices of $H$ which are constrained such that any edge has at least $α$ and at most $β$ vertices of the same colour, and we have shown that interesting results can be obtained by varying $α, β$ and the parameters of $H$ appropriately. In this paper we continue to investigate the versatility of $σ$-hypergraphs by considering two classical problems: independence and matchings. We first demonstrate an interesting link between the constrained colourings described above and the $k$-independence number of a hypergraph, that is, the largest cardinality of a subset of vertices of a hypergraph not containing $k+1$ vertices in the same edge. We also give an exact computation of the $k$-independence number of the $σ$-hypergraph $H$. We then present results on maximum, and sometimes perfect, matchings in $H$. These results often depend on divisibility relations between the parameters of $H$ and on the highest common factor of the parts of $σ$.
A degree monotone path in a graph $G$ is a path $P$ such that the sequence of degrees of the vertices in the order in which they appear on $P$ is monotonic. The length of the longest degree monotone path in $G$ is denoted by $mp(G)$. This parameter, inspired by the well-known Erdos-Szekeres theorem, has been studied by the authors in two earlier papers. Here we consider a saturation problem for the parameter $mp(G)$. We call $G$ saturated if, for every edge $e$ added to $G$, $mp(G+e) >mp(G)$, and we define $h(n,k)$ to be the least possible number of edges in a saturated graph $G$ on $n$ vertices with $mp(G) < k$, while $mp(G+e) \geq k$ for every new edge $e$. We obtain linear lower and upper bounds for $h(n,k)$, we determine exactly the values of $h(n,k)$ for $k=3$ and $4$, and we present constructions of saturated graphs.
In this paper, we first establish the very close link between stability of graphs, a concept first introduced in \cite{Scapsalvi1} and studied most notably by Surowski \cite{Surowski1}, \cite{Surowski2} and Wilson \cite{Wilson01} and two-fold automorphisms. The concept of two-fold isomorphisms, as far as we know, first appeared in literature in the form of isotopies of digraphs \cite{zelinka4}, \cite{zelinka1}, \cite{zelinka2}, \cite{zelinka3} and later studied formally in \cite{lms1}, \cite{lms2} with a greater emphasis on undirected graphs. We then turn our attention to the stability of graphs which have every edge on a triangle, but with the fresh outlook provided by TF-automorphisms. Amongst such graphs are strongly regular graphs with certain parameters. The advantages of this fresh outlook are highlighted when we ultimately present a method of constructing and generating unstable graphs with large diameter having every edge lying on a triangle. This was a rather surprising outcome.
One of the most interesting new developments in hypergraph colourings in these last few years has been Voloshin's notion of colourings of mixed hypergraphs. In this paper we shall study a specific instance of Voloshin's idea: a non-monochromatic non-rainbow (NMNR) colouring of a hypergraph is a colouring of its vertices such that every edge has at least two vertices coloured with different colours (non-monochromatic) and no edge has all of its vertices coloured with distinct colours (non-rainbow). Perhaps the most intriguing phenomenon of such colourings is that a hypergraph can have gaps in its NMNR chromatic spectrum, that is, for some $k_1 < k_2 < k_3$, the hypergraph is NMNR colourable with $k_1$ and with $k_3$ colours but not with $k_2$ colours. Several beautiful examples have been constructed of NMNR colourings of hypergraphs exhibiting phenomena not seen in classical colourings. Many of these examples are either \emph{ad hoc} or else are based on designs. The latter are difficult to construct and they generally give uniform $r$-hypergraphs only for low values of $r$, generally $r=3$. In this paper we shall study the NMNR colourings of a type of $r$-uniform hypergraph which we call $σ$-hypergraphs. The attractive feature of these $σ$-hypergraphs is that they are easy to define, even for large $r$, and that, by suitable modifications of their parameters, they can give families of hypergraphs which are guaranteed to have NMNR spectra with gaps or NMNR spectra without gaps. These $σ$-hypergraphs also team up very well with the notion of colour-bounded hypergraphs recently introduced by Bujt{á}s and Tuza to give further control on the appearance of gaps and perhaps explain better the existence of gaps in the colouring of mixed hypergraphs.
The edge-reconstruction number ern$(G)$ of a graph $G$ is equal to the minimum number of edge-deleted subgraphs $G-e$ of $G$ which are sufficient to determine $G$ up to isomorphsim. Building upon the work of Molina and using results from computer searches by Rivshin and more recent ones which we carried out, we show that, apart from three known exceptions, all bicentroidal trees have edge-reconstruction number equal to 2. We also exhibit the known trees having edge-reconstruction number equal to 3 and we conjecture that the three infinite families of unicentroidal trees which we have found to have edge-reconstruction number equal to 3 are the only ones.