Researcher profile

Christina Zarb

Christina Zarb contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate

math.CO

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author

10works

0followers

1topics

3close collaborators

Actions

Decide how to stay connected

Follow researcher0

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

Index of Parameters of Iterated Line Graphs

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.

preprint2022arXiv

The feasibility problem for line graphs

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.

preprint2020arXiv

On small balanceable, strongly-balanceable and omnitonal graphs

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.

preprint2020arXiv

On zero-sum spanning trees and zero-sum connectivity

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.

preprint2014arXiv

$(2,2)$-colourings and clique-free $σ$-hypergraphs

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.

preprint2014arXiv

Constrained colouring and $σ$-hypergraphs

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.

preprint2014arXiv

Degree Monotone Paths

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.

preprint2014arXiv

Degree Monotone Paths and Graph Operations

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.

preprint2014arXiv

Hamiltonicity and $σ$-hypergraphs

We define and study a special type of hypergraph. A $σ$-hypergraph $H= H(n,r,q$ $\mid$ $σ$), where $σ$ is a partition of $r$, is an $r$-uniform hypergraph having $nq$ vertices partitioned into $ n$ classes of $q$ vertices each. If the classes are denoted by $V_1$, $V_2$,...,$V_n$, then a subset $K$ of $V(H)$ of size $r$ is an edge if the partition of $r$ formed by the non-zero cardinalities $ \mid$ $K$ $\cap$ $V_i \mid$, $ 1 \leq i \leq n$, is $σ$. The non-empty intersections $K$ $\cap$ $V_i$ are called the parts of $K$, and $s(σ)$ denotes the number of parts. We consider various types of cycles in hypergraphs such as Berge cycles and sharp cycles in which only consecutive edges have a nonempty intersection. We show that most $σ$-hypergraphs contain a Hamiltonian Berge cycle and that, for $n \geq s+1$ and $q \geq r(r-1)$, a $σ$-hypergraph $H$ always contains a sharp Hamiltonian cycle. We also extend this result to $k$-intersecting cycles.

preprint2014arXiv

Independence and Matchings in $σ$-hypergraphs

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

Institution

Affiliation not imported yet

This author record came from a source that does not expose affiliation metadata. Once the author claims the profile or we enrich the record from another provider, this section will link to the concrete institution.

Topic footprint