Every cycle-connected multipartite tournament has a universal arc

A digraph D is cycle-connected if for every pair of vertices u,v∈V(D) there exists a directed cycle in D containing both u and v. In 1999, Ádám [A. Ádám, On some cyclic connectivity properties of directed graphs, Acta Cybernet. 14 (1) (1999) 1-12] posed the following problem. Let D be a cycle-connected digraph. Does there exist a universal arc in D, i.e., an arc e∈A(D) such that for every vertex w∈V(D) there is a directed cycle in D containing both e and w?A c-partite or multipartite tournament is an orientation of a complete c-partite graph. Recently, Hubenko [A. Hubenko, On a cyclic connectivity property of directed graphs, Discrete Math. 308 (2008) 1018-1024] proved that each cycle-connected bipartite tournament has a universal arc. As an extension of this result, we show in this note that each cycle-connected multipartite tournament has a universal arc.     

Every Cycle-Connected Multipartite Tournament with δ ≥ 2 Contains At Least Two Universal Arcs

A digraph D = (V(D), A(D)) is called cycle-connected if for every pair of vertices ${u, v\in V(D)}$ there exists a cycle containing both u and v. Ádám (Acta Cybernet 14(1):1–12, 1999) proposed the question: Let D be a cycle-connected digraph. Does there exist a universal arc in D, i.e., an arc ${e\in A(D)}$ such that for every vertex ${w\in V(D)}$ there exists a cycle C in D containing both e and w?. Recently, Lutz Volkmann and Stefan Winzen have proved that this conjecture is true for multipartite tournaments. As an improvement of this result, we show in this note that every cycle-connected multipartite tournament with δ ≥ 2 contains at least two universal arcs.     

Kernels in quasi-transitive digraphs

Let D be a digraph, V(D) and A(D) will denote the sets of vertices and arcs of D, respectively.A kernel N of D is an independent set of vertices such that for every w∈V(D)-N there exists an arc from w to N. A digraph is called quasi-transitive when (u,v)∈A(D) and (v,w)∈A(D) implies (u,w)∈A(D) or (w,u)∈A(D). This concept was introduced by Ghouilá-Houri [Caractérisation des graphes non orientés dont on peut orienter les arrêtes de maniere à obtenir le graphe d’ un relation d’ordre, C.R. Acad. Sci. Paris 254 (1962) 1370-1371] and has been studied by several authors. In this paper the following result is proved: Let D be a digraph. Suppose D=D₁∪D₂ where D_i is a quasi-transitive digraph which contains no asymmetrical infinite outward path (in D_i) for i∈{1,2}; and that every directed cycle of length 3 contained in D has at least two symmetrical arcs, then D has a kernel. All the conditions for the theorem are tight.     

Characterization of digraphs with equal domination graphs and underlying graphs

A domination graph of a digraph D, dom(D), is created using the vertex set of D and edge {u,v}∈E[dom(D)] whenever (u,z)∈A(D) or (v,z)∈A(D) for every other vertex z∈V(D). The underlying graph of a digraph D, UG(D), is the graph for which D is a biorientation. We completely characterize digraphs whose underlying graphs are identical to their domination graphs, UG(D)=dom(D). The maximum and minimum number of single arcs in these digraphs, and their characteristics, is given.     

Kernels and some operations in edge-coloured digraphs

Let D be an edge-coloured digraph, V(D) will denote the set of vertices of D; a set N⊆V(D) is said to be a kernel by monochromatic paths of D if it satisfies the following two conditions: For every pair of different vertices u,v∈N there is no monochromatic directed path between them and; for every vertex x∈V(D)−N there is a vertex y∈N such that there is an xy-monochromatic directed path.In this paper we consider some operations on edge-coloured digraphs, and some sufficient conditions for the existence or uniqueness of kernels by monochromatic paths of edge-coloured digraphs formed by these operations from another edge-coloured digraphs.     

The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops

For digraphs D and H, a mapping f:V(D)→V(H) is a homomorphism of D to H if uv∈A(D) implies f(u)f(v)∈A(H). For a fixed digraph H, the homomorphism problem is to decide whether an input digraph D admits a homomorphism to H or not, and is denoted as HOM(H).An optimization version of the homomorphism problem was motivated by a real-world problem in defence logistics and was introduced in Gutin, Rafiey, Yeo and Tso (2006) [13]. If each vertex u∈V(D) is associated with costs c_i(u),i∈V(H), then the cost of the homomorphism f is ∑_u∈V(D)c_f(u)(u). For each fixed digraph H, we have the minimum cost homomorphism problem forH and denote it as MinHOM(H). The problem is to decide, for an input graph D with costs c_i(u),u∈V(D),i∈V(H), whether there exists a homomorphism of D to H and, if one exists, to find one of minimum cost.Although a complete dichotomy classification of the complexity of MinHOM(H) for a digraph H remains an unsolved problem, complete dichotomy classifications for MinHOM(H) were proved when H is a semicomplete digraph Gutin, Rafiey and Yeo (2006) [10], and a semicomplete multipartite digraph Gutin, Rafiey and Yeo (2008) [12] and [11]. In these studies, it is assumed that the digraph H is loopless. In this paper, we present a full dichotomy classification for semicomplete digraphs with possible loops, which solves a problem in Gutin and Kim (2008) [9].     

Minimum cost homomorphisms to semicomplete multipartite digraphs

For digraphs D and H, a mapping f:V(D)→V(H) is a homomorphism ofDtoH if uv∈A(D) implies f(u)f(v)∈A(H). For a fixed directed or undirected graph H and an input graph D, the problem of verifying whether there exists a homomorphism of D to H has been studied in a large number of papers. We study an optimization version of this decision problem. Our optimization problem is motivated by a real-world problem in defence logistics and was introduced recently by the authors and M. Tso.Suppose we are given a pair of digraphs D,H and a cost c_i(u) for each u∈V(D) and i∈V(H). The cost of a homomorphism f of D to H is ∑_u∈V(D)c_f(u)(u). Let H be a fixed digraph. The minimum cost homomorphism problem for H, MinHOMP(H), is stated as follows: For input digraph D and costs c_i(u) for each u∈V(D) and i∈V(H), verify whether there is a homomorphism of D to H and, if it does exist, find such a homomorphism of minimum cost. In our previous paper we obtained a dichotomy classification of the time complexity of when H is a semicomplete digraph. In this paper we extend the classification to semicomplete k-partite digraphs, k≥3, and obtain such a classification for bipartite tournaments.     

Kernels in edge-coloured orientations of nearly complete graphs

We call the digraph D an orientation of a graph G if D is obtained from G by the orientation of each edge of G in exactly one of the two possible directions. The digraph D is an m-coloured digraph if the arcs of D are coloured with m-colours.Let D be an m-coloured digraph. A directed path (or a directed cycle) is called monochromatic if all of its arcs are coloured alike.A set N⊆V(D) is said to be a kernel by monochromatic paths if it satisfies the two following conditions: (i) for every pair of different vertices u,v∈N there is no monochromatic directed path between them and (ii) for every vertex x∈V(D)-N there is a vertex y∈N such that there is an xy-monochromatic directed path.In this paper we obtain sufficient conditions for an m-coloured orientation of a graph obtained from K_n by deletion of the arcs of K_1,r(0?r?n-1) to have a kernel by monochromatic.     

Some sufficient conditions for the existence of kernels in infinite digraphs

A kernel N of a digraph D is an independent set of vertices of D such that for every w∈V(D)−N there exists an arc from w to N. If every induced subdigraph of D has a kernel, D is said to be a kernel perfect digraph. D is called a critical kernel imperfect digraph when D has no kernel but every proper induced subdigraph of D has a kernel. If F is a set of arcs of D, a semikernel modulo F of D is an independent set of vertices S of D such that for every z∈V(D)−S for which there exists an (S,z)-arc of D−F, there also exists an (z,S)-arc in D. In this work we show sufficient conditions for an infinite digraph to be a kernel perfect digraph, in terms of semikernel modulo F. As a consequence it is proved that symmetric infinite digraphs and bipartite infinite digraphs are kernel perfect digraphs. Also we give sufficient conditions for the following classes of infinite digraphs to be kernel perfect digraphs: transitive digraphs, quasi-transitive digraphs, right (or left)-pretransitive digraphs, the union of two right (or left)-pretransitive digraphs, the union of a right-pretransitive digraph with a left-pretransitive digraph, the union of two transitive digraphs, locally semicomplete digraphs and outward locally finite digraphs.     

Subdivided trees are integral sum graphs

A graph G=(V,E) is an integral sum graph (ISG) if there exists a labeling S(G)⊂Z such that V=S(G) and for every pair of distinct vertices u,v∈V, uv is an edge if and only if u+v∈V. A vertex in a graph is called a fork if its degree is not 2. In 1998, Chen proved that every tree whose forks are at distance at least 4 from each other is an ISG. In 2004, He et al. reduced the distance to 3. In this paper we reduce the distance further to 2, i.e. we prove that every tree whose forks are at least distance 2 apart is an ISG.     

Hamilton cycles in digraphs of unitary matrices

A set S⊆V is called a q⁺-set (q^--set, respectively) if S has at least two vertices and, for every u∈S, there exists v∈S,v≠u such that N⁺(u)∩N⁺(v)≠∅ (N^-(u)∩N^-(v)≠∅, respectively). A digraph D is called s-quadrangular if, for every q⁺-set S, we have |∪{N⁺(u)∩N⁺(v):u≠v,u,v∈S}|?|S| and, for every q^--set S, we have |∪{N^-(u)∩N^-(v):u,v∈S)}?|S|. We conjecture that every strong s-quadrangular digraph has a Hamilton cycle and provide some support for this conjecture.     

Minimum cost and list homomorphisms to semicomplete digraphs

For digraphs D and H, a mapping f:V(D)→V(H) is a homomorphism of D to H if uv∈A(D) implies f(u)f(v)∈A(H). Let H be a fixed directed or undirected graph. The homomorphism problem for H asks whether a directed or undirected input graph D admits a homomorphism to H. The list homomorphism problem for H is a generalization of the homomorphism problem for H, where every vertex x∈V(D) is assigned a set L_x of possible colors (vertices of H).The following optimization version of these decision problems generalizes the list homomorphism problem and was introduced in Gutin et al. [Level of repair analysis and minimum cost homomorphisms of graphs, Discrete Appl. Math., to appear], where it was motivated by a real-world problem in defence logistics. Suppose we are given a pair of digraphs D,H and a positive integral cost c_i(u) for each u∈V(D) and i∈V(H). The cost of a homomorphism f of D to H is . For a fixed digraph H, the minimum cost homomorphism problem for H is stated as follows: for an input digraph D and costs c_i(u) for each u∈V(D) and i∈V(H), verify whether there is a homomorphism of D to H and, if one exists, find such a homomorphism of minimum cost.We obtain dichotomy classifications of the computational complexity of the list homomorphism and minimum cost homomorphism problems, when H is a semicomplete digraph (digraph in which there is at least one arc between any two vertices). Our dichotomy for the list homomorphism problem coincides with the one obtained by Bang-Jensen, Hell and MacGillivray in 1988 for the homomorphism problem when H is a semicomplete digraph: both problems are polynomial solvable if H has at most one cycle; otherwise, both problems are NP-complete. The dichotomy for the minimum cost homomorphism problem is different: the problem is polynomial time solvable if H is acyclic or H is a cycle of length 2 or 3; otherwise, the problem is NP-hard.     

Ultracritical and hypercritical binary structures

A binary structure is an arc-coloured complete digraph, without loops, and with exactly two coloured arcs (u,v) and (v,u) between distinct vertices u and v. Graphs, digraphs and partial orders are all examples of binary structures. Let B be a binary structure. With each subset W of the vertex set V(B) of B we associate the binary substructure B[W] of B induced by W. A subset C of V(B) is a clan of B if for any c,d∈C and v∈V(B)?C, the arcs (c,v) and (d,v) share the same colour and similarly for (v,c) and (v,d). For instance, the vertex set V(B), the empty set and any singleton subset of V(B) are clans of B. They are called the trivial clans of B. A binary structure is primitive if all its clans are trivial.With a primitive and infinite binary structure B we associate a criticality digraph (in the sense of [11]) defined on V(B) as follows. Given v≠w∈V(B), (v,w) is an arc of the criticality digraph of B if v belongs to a non-trivial clan of B[V(B)?{w}]. A primitive and infinite binary structure B is finitely critical if B[V(B)?F] is not primitive for each finite and non-empty subset F of V(B). A finitely critical binary structure B is hypercritical if for every v∈V(B), B[V(B)?{v}] admits a non-trivial clan C such that |V(B)?C|≥3 which contains every non-trivial clan of B[V(B)?{v}]. A hypercritical binary structure is ultracritical whenever its criticality digraph is connected.The ultracritical binary structures are studied from their criticality digraphs. Then a characterization of the non-ultracritical but hypercritical binary structures is obtained, using the generalized quotient construction originally introduced in [1].     

On CCE graphs of doubly partial orders

Let D be a digraph. The competition-common enemy graph (CCE graph) of D has the same set of vertices as D and an edge between vertices u and v if and only if there are vertices w and x in D such that (w,u), (w,v), (u,x), and (v,x) are arcs of D. We call a graph a CCE graph if it is the CCE graph of some digraph. In this paper, we show that if the CCE graph of a doubly partial order does not contain C₄ as an induced subgraph, it is an interval graph. We also show that any interval graph together with enough isolated vertices is the CCE graph of some doubly partial order.     

Cycle-magic graphs

A simple graph G=(V,E) admits a cycle-covering if every edge in E belongs at least to one subgraph of G isomorphic to a given cycle C. Then the graph G is C-magic if there exists a total labelling f:V∪E→{1,2,…,|V|+|E|} such that, for every subgraph H^′=(V^′,E^′) of G isomorphic to C, ∑_v∈V^′f(v)+∑_e∈E^′f(e) is constant. When f(V)={1,…,|V|}, then G is said to be C-supermagic.We study the cyclic-magic and cyclic-supermagic behavior of several classes of connected graphs. We give several families of C_r-magic graphs for each r?3. The results rely on a technique of partitioning sets of integers with special properties.     

On distance two graphs of upper bound graphs

For a poset P=(X,≤), the upper bound graph (UB-graph) of P is the graph U=(X,E_U), where uv∈E_U if and only if u≠v and there exists m∈X such that u,v≤m. For a graph G, the distance two graph DS₂(G) is the graph with vertex set V(DS₂(G))=V(G) and u,v∈V(DS₂(G)) are adjacent if and only if d_G(u,v)=2. In this paper, we deal with distance two graphs of upper bound graphs. We obtain a characterization of distance two graphs of split upper bound graphs.     

Degree sum conditions for oriented forests in digraphs

Let F be an oriented forest with n vertices and m arcs and D be a digraph without loops and multiple arcs. In this note we prove that D contains a subdigraph isomorphic to F if D has at least n vertices and min{d⁺(u)+d⁺(v),d⁻(u)+d⁻(v),d⁺(u)+d⁻(v)}≥2m−1 for every pair of vertices u,v∈V(D) with uv∉A(D). This is a common generalization of two results of Babu and Diwan, one on the existence of forests in graphs under a degree sum condition and the other on the existence of oriented forests in digraphs under a minimum degree condition.     

Signed star domatic number of a graph

Let G be a simple graph without isolated vertices with vertex set V(G) and edge set E(G). A function f:E(G)?{−1,1} is said to be a signed star dominating function on G if ∑_e∈E(v)f(e)≥1 for every vertex v of G, where E(v)={uv∈E(G)∣u∈N(v)}. A set {f₁,f₂,…,f_d} of signed star dominating functions on G with the property that for each e∈E(G), is called a signed star dominating family (of functions) on G. The maximum number of functions in a signed star dominating family on G is the signed star domatic number of G, denoted by d_SS(G).In this paper we study the properties of the signed star domatic number d_SS(G). In particular, we determine the signed domatic number of some classes of graphs.     

Enumerations of vertex orders of almost Moore digraphs with selfrepeats

An almost Moore digraph G of degree d>1, diameter k>1 is a diregular digraph with the number of vertices one less than the Moore bound. If G is an almost Moore digraph, then for each vertex u∈V(G) there exists a vertex v∈V(G), called repeat of u and denoted by r(u)=v, such that there are two walks of length ?k from u to v. The smallest positive integer p such that the composition r^p(u)=u is called the order of u. If the order of u is 1 then u is called a selfrepeat. It is known that if G is an almost Moore digraph of diameter k?3 then G contains exactly k selfrepeats or none. In this paper, we propose an exact formula for the number of all vertex orders in an almost Moore digraph G containing selfrepeats, based on the vertex orders of the out-neighbours of any selfrepeat vertex.     

On the structure of strong 3-quasi-transitive digraphs

In this paper, D=(V(D),A(D)) denotes a loopless directed graph (digraph) with at most one arc from u to v for every pair of vertices u and v of V(D). Given a digraph D, we say that D is 3-quasi-transitive if, whenever u→v→w→z in D, then u and z are adjacent or u=z. In Bang-Jensen (2004) [3], Bang-Jensen introduced 3-quasi-transitive digraphs and claimed that the only strong 3-quasi-transitive digraphs are the strong semicomplete digraphs and strong semicomplete bipartite digraphs. In this paper, we exhibit a family of strong 3-quasi-transitive digraphs distinct from strong semicomplete digraphs and strong semicomplete bipartite digraphs and provide a complete characterization of strong 3-quasi-transitive digraphs.