Search

Let $D$ be an oriented graph. The inversion of a set $X$ of vertices in $D$ consists in reversing the direction of all arcs with both ends in $X$. The inversion number of $D$, denoted by ${\rm inv}(D)$, is the minimum number of inversions needed to make $D$ acyclic. Denoting by $\tau(D)$, $\tau' (D)$, and $\nu(D)$ the cycle transversal number, the cycle arc-transversal number and the cycle packing number of $D$ respectively, one shows that ${\rm inv}(D) \leq \tau' (D)$, ${\rm inv}(D) \leq 2\tau(D)$ and there exists a function $g$ such that ${\rm inv}(D)\leq g(\nu(D))$. We conjecture that for any two oriented graphs $L$ and $R$, ${\rm inv}(L\rightarrow R) ={\rm inv}(L) +{\rm inv}(R)$ where $L\rightarrow R$ is the dijoin of $L$ and $R$. This would imply that the first two inequalities are tight. We prove this conjecture when ${\rm inv}(L)\leq 1$ and ${\rm inv}(R)\leq 2$ and when ${\rm inv}(L) ={\rm inv}(R)=2$ and $L$ and $R$ are strongly connected. We also show that the function $g$ of the third inequality satisfies $g(1)\leq 4$. We then consider the complexity of deciding whether ${\rm inv}(D)\leq k$ for a given oriented graph $D$. We show that it is NP-complete for $k=1$, which together with the above conjecture would imply that it is NP-complete for every $k$. This contrasts with a result of Belkhechine et al. which states that deciding whether ${\rm inv}(T)\leq k$ for a given tournament $T$ is polynomial-time solvable.

Ear decompositions of graphs are a standard concept related to several major problems in graph theory like the Traveling Salesman Problem. For example, the Hamiltonian Cycle Problem, which is notoriously N P-complete, is equivalent to deciding whether a given graph admits an ear decomposition in which all ears except one are trivial (i.e. of length 1). On the other hand, a famous result of Lovász states that deciding whether a graph admits an ear decomposition with all ears of odd length can be done in polynomial time. In this paper, we study the complexity of deciding whether a graph admits an ear decomposition with prescribed ear lengths. We prove that deciding whether a graph admits an ear decomposition with all ears of length at most is polynomial-time solvable for all fixed positive integer. On the other hand, deciding whether a graph admits an ear decomposition without ears of length in F is N P-complete for any finite set F of positive integers. We also prove that, for any k ≥ 2, deciding whether a graph admits an ear decomposition with all ears of length 0 mod k is N P-complete. We also consider the directed analogue to ear decomposition, which we call handle decomposition, and prove analogous results : deciding whether a digraph admits a handle decomposition with all handles of length at most is polynomial-time solvable for all positive integer ; deciding whether a digraph admits a handle decomposition without handles of length in F is N P-complete for any finite set F of positive integers (and minimizing the number of handles of length in F is not approximable up to n(1 −)); for any k ≥ 2, deciding whether a digraph admits a handle decomposition with all handles of length 0 mod k is N P-complete. Also, in contrast with the result of Lovász, we prove that deciding whether a digraph admits a handle decomposition with all handles of odd length is N P-complete. Finally, we conjecture that, for every set A of integers, deciding whether a digraph has a handle decomposition with all handles of length in A is N P-complete, unless there exists h ∈ N such that A = {1, · · · , h}.

We investigate graph colouring models for the purpose of optimizing TDMA link scheduling in Wireless Networks. Inspired by the BPRN-colouring model recently introduced by Rocha and Sasaki, we introduce a new colouring model, namely the BMRN-colouring model, which can be used to model link scheduling problems where particular types of collisions must be avoided during the node transmissions. In this paper, we initiate the study of the BMRN-colouring model by providing several bounds on the minimum number of colours needed to BMRN-colour digraphs, as well as several complexity results establishing the hardness of finding optimal colourings. We also give a special focus on these considerations for planar digraph topologies, for which we provide refined results.

Graph Theory

For a connected graph G of order |V(G)| ≥3 and a k-labelling c : E(G) →{1,2,…,k} of the edges of G, the code of a vertex v of G is the ordered k-tuple (ℓ1,ℓ2,…,ℓk), where ℓi is the number of edges incident with v that are labelled i. The k-labelling c is detectable if every two adjacent vertices of G have distinct codes. The minimum positive integer k for which G has a detectable k-labelling is the detection number det(G) of G. In this paper, we show that it is NP-complete to decide if the detection number of a cubic graph is 2. We also show that the detection number of every bipartite graph of minimum degree at least 3 is at most 2. Finally, we give some sufficient condition for a cubic graph to have detection number 3.

A natural generalization of graph colouring involves taking colours from a metric space and insisting that the endpoints of an edge receive colours separated by a minimum distance dictated by properties of the edge. In the q-backbone colouring problem, these minimum distances are either q or 1, depending on whether or not the edge is in the backbone. In this paper we consider the list version of this problem, with particular focus on colours in ℤp - this problem is closely related to the problem of circular choosability. We first prove that the list circular q-backbone chromatic number of a graph is bounded by a function of the list chromatic number. We then consider the more general problem in which each edge is assigned an individual distance between its endpoints, and provide bounds using the Combinatorial Nullstellensatz. Through this result and through structural approaches, we achieve good bounds when both the graph and the backbone belong to restricted families of graphs.