Weakly Cycle Complementary 3-Partite Tournaments

The vertex set of a digraph D is denoted by V(D). A c-partite tournament is an orientation of a complete c-partite graph. Let V ₁, V ₂, . . . ,V _c be the partite sets of D. If there exist two vertex disjoint cycles C and C′ in D such that V_i?(V(C)èV(C￠)) 1 ?{V_{\mathrm{i}}\cap(V(C)\cup V(C'))\neq\emptyset} for all i = 1, 2, . . . , c, then D is weakly cycle complementary. In 2008, Volkmann and Winzen gave the above definition of weakly complementary cycles and proved that all 3-connected c-partite tournaments with c ≥ 3 are weakly cycle complementary. In this paper, we characterize multipartite tournaments are weakly cycle complementary. Especially, we show that all 2-connected 3-partite tournaments that are weakly cycle complementary, unless D is isomorphic to D _3,2, D _3,2,2 or D _3,3,1.     

Complementary cycles in regular multipartite tournaments, where one cycle has length five

The vertex set of a digraph D is denoted by V(D). A c-partite tournament is an orientation of a complete c-partite graph.In 1999, Yeo conjectured that each regular c-partite tournament D with c≥4 and |V(D)|≥10 contains a pair of vertex disjoint directed cycles of lengths 5 and |V(D)|−5. In this paper we shall confirm this conjecture using a computer program for some cases.     

Line-digraphs,arborescences, and theorems of tutte and knuth

The line-digraph of a digraph D with vertices V₁, …, V_n is the digraph $\text{D}{}^1$ obtained from D by associating with each edge of D a vertex of $\text{D}{}^1$, and then directing an edge from vertex (V_i, V_j) of $\text{D}{}^1$ to vertex (V_k, V_m) if and only if j = k. This paper extends a characterization given by Harary and Norman for linedigraphs. It is also possible to repeatedly contract vertices of the line-digraph (with a new contraction procedure) so as to obtain the digraph derived from D by deleting all vertices with no incoming edges. Several new identities for arborescences are presented, leading to a combinatorial proof of Knuth's formula for the number of arborescences of a line-digraph. A new proof is given for the fact that in a digraph with every vertex having indegree equal to outdegree, the number of arborescences with root V_j is independent of j. Finally a new proof is presented for Tutte's Matrix Tree Theorem which shows the theorem to be a special case of the principle of inclusion-exclusion.     

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].     

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.     

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.     

Longest cycles in almost regular 3-partite tournaments

If D is a digraph, then we denote by V(D) its vertex set. A multipartite or c-partite tournament is an orientation of a complete c-partite graph. The global irregularity of a digraph D is defined by

     

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.     

On cycles in regular 3-partite tournaments

The vertex set of a digraph D is denoted by V(D). A c-partite tournament is an orientation of a complete c-partite graph. In 1991, Jian-zhong Wang conjectured that every arc of a regular 3-partite tournament D is contained in directed cycles of all lengths 3,6,9,…,|V(D)|. This conjecture is not valid, because for each integer t with 3?t?|V(D)|, there exists an infinite family of regular 3-partite tournaments D such that at least one arc of D is not contained in a directed cycle of length t.In this paper, we prove that every arc of a regular 3-partite tournament with at least nine vertices is contained in a directed cycle of length m, m+1, or m+2 for 3?m?5, and we conjecture that every arc of a regular 3-partite tournament is contained in a directed cycle of length m, (m+1), or (m+2) for each m∈{3,4,…,|V(D)|-2}.It is known that every regular 3-partite tournament D with at least six vertices contains directed cycles of lengths 3, |V(D)|-3, and |V(D)|. We show that every regular 3-partite tournament D with at least six vertices also has a directed cycle of length 6, and we conjecture that each such 3-partite tournament contains cycles of all lengths 3,6,9,…,|V(D)|.     

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.     

The elimination procedure for the competition number is not optimal

Given an acyclic digraph D, the competition graph C(D) is defined to be the undirected graph with V(D) as its vertex set and where vertices x and y are adjacent if there exists another vertex z such that the arcs (x,z) and (y,z) are both present in D. The competition number k(G) for an undirected graph G is the least number r such that there exists an acyclic digraph F on |V(G)|+r vertices where C(F) is G along with r isolated vertices. Kim and Roberts [The Elimination Procedure for the Competition Number, Ars Combin. 50 (1998) 97-113] introduced an elimination procedure for the competition number, and asked whether the procedure calculated the competition number for all graphs. We answer this question in the negative by demonstrating a graph where the elimination procedure does not calculate the competition number. This graph also provides a negative answer to a similar question about the related elimination procedure for the phylogeny number introduced by the current author in [S.G. Hartke, The Elimination Procedure for the Phylogeny Number, Ars Combin. 75 (2005) 297-311].     

On a characterization of irreducibility of a non-negative matrix

Let A denote an n×n matrix with all its elements real and non-negative, and let r_i be the sum of the elements in the ith row of A, i=1,…,n. Let B=A?D(r₁,…,r_n), where D(r₁,…,r_n) is the diagonal matrix with r_i at the position (i,i). Then it is proved that A is irreducible if and only if rank B=n?1 and the null space of B^T contains a vector d whose entries are all non-null.     

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.     

Dimension-2 poset competition numbers and dimension-2 poset double competition numbers

Let D=(V(D),A(D)) be a digraph. The competition graph of D, is the graph with vertex set V(D) and edge set . The double competition graph of D, is the graph with vertex set V(D) and edge set . A poset of dimension at most two is a digraph whose vertices are some points in the Euclidean plane R² and there is an arc going from a vertex (x₁,y₁) to a vertex (x₂,y₂) if and only if x₁>x₂ and y₁>y₂. We show that a graph is the competition graph of a poset of dimension at most two if and only if it is an interval graph, at least half of whose maximal cliques are isolated vertices. This answers an open question on the doubly partial order competition number posed by Cho and Kim. We prove that the double competition graph of a poset of dimension at most two must be a trapezoid graph, generalizing a result of Kim, Kim, and Rho. Some connections are also established between the minimum numbers of isolated vertices required to be added to change a given graph into the competition graph, the double competition graph, of a poset and the minimum sizes of certain intersection representations of that graph.     

Hamilton cycles,avoiding prescribed arcs,in close-to-regular tournaments

The local irregularity of a digraph D is defined as i_l(D) = max {|d⁺ (x) − d⁻ (x)| : x ϵ V(D)}. Let T be a tournament, let Γ = {V₁, V₂, …, V_c} be a partition of V(T) such that |V₁| ≥ |V₂| ≥ … ≥ |V_c|, and let D be the multipartite tournament obtained by deleting all the arcs with both end points in the same set in Γ. We prove that, if |V(T)| ≥ max{2i_l(T) + 2|V₁| + 2|V₂| − 2, i_l(T) + 3|V₁| − 1}, then D is Hamiltonian. Furthermore, if T is regular (i.e., i_l(T) = 0), then we state slightly better lower bounds for |V(T)| such that we still can guarantee that D is Hamiltonian. Finally, we show that our results are best possible. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 123–136, 1999     

Amalgamations of almost regular edge-colourings of simple graphs

A finite graph F is a detachment of a finite graph G if G can be obtained from F by partitioning V(F) into disjoint sets S₁, …, S_n and identifying the vertices in S_i to form a single vertex α_i for i = 1, …, n. Thus E(F) = E(G) and an edge which joins an element of S_i to an element of S_j in F will join α_i to α_j in G. If L is a subset of E(G) then G(L) denotes the subgraph of G such that V(G(L)) = V(G), E(G(L)) = L. We call a graph almost regular if there is an integer d such that every vertex has valency d or d + 1. Suppose that E(G) is partitioned into disjoint sets E₁, …, E_r. Hilton [3] found necessary and sufficient conditions for the existence of a detachment F of G such that F is a complete graph with 2r + 1 vertices and F(E_i) is a Hamilton circuit of F for i = 1, …, r. We give a new proof of Hilton's theorem, which also yields a generalisation. Specifically, for any q ∈ {0, 1, …, r}, we find necessary and sufficient conditions for G to have a detachment F without loops or multiple edges such that F(E₁), …, F(E_r) are almost regular and F(E₁), …, F(E_q) are 2-edge-connected and each vertex ξ of G arises by identification from a prescribed number g(ξ) of vertices of F.     

Cycles with a given number of vertices from each partite set in regular multipartite tournaments

If x is a vertex of a digraph D, then we denote by d ⁺(x) and d ⁻(x) the outdegree and the indegree of x, respectively. A digraph D is called regular, if there is a number p ∈ ℕ such that d ⁺(x) = d ⁻(x) = p for all vertices x of D. A c-partite tournament is an orientation of a complete c-partite graph. There are many results about directed cycles of a given length or of directed cycles with vertices from a given number of partite sets. The idea is now to combine the two properties. In this article, we examine in particular, whether c-partite tournaments with r vertices in each partite set contain a cycle with exactly r − 1 vertices of every partite set. In 1982, Beineke and Little [2] solved this problem for the regular case if c = 2. If c ⩾ 3, then we will show that a regular c-partite tournament with r ⩾ 2 vertices in each partite set contains a cycle with exactly r − 1 vertices from each partite set, with the exception of the case that c = 4 and r = 2.     

Spectral radius of digraphs with given dichromatic number

Let D be a digraph with vertex set V(D). A partition of V(D) into k acyclic sets is called a k-coloring of D. The minimum integer k for which there exists a k-coloring of D is the dichromatic number χ(D) of the digraph D. Denote G_n,k the set of the digraphs of order n with the dichromatic number k≥2. In this note, we characterize the digraph which has the maximal spectral radius in G_n,k. Our result generalizes the result of [8] by Feng et al.     

An Extremal Problem on v-Partite Graphs

Let r, t, and v be positive integers with 2 ? t ? v. For a fixed graph G with t vertices, denote by Г (r, v, G) the class of all v-partite graphs H with vertex classes V_i, |V_i| = r (i =1, 2, ... , v) satisfying the following condition: For every t-subset {i₁, i₂, ... , i_t} of {1, 2, ... , v} there exists a subgraph of H isomorphic to G having exactly one vertex in each of the classes V_iτ, τ =1, 2, ... , t. Let cl(H) denote the clique number of H, i.e. the maximum order of a complete subgraph of H. We are interested in determining the value of the class parameter

$D(r,v,G)=\underset{H\in \Gamma (r,v,G)}{\min }cl(H)$

The main result is given the form of a Ramsey-type theorem (see Theorem 2.2). We shall show that for fixed r and G, D (r, v, G) tends to infinity when v tends to infinity if and only if χ(G) (the chromatic number of G) is greater than r. Some results concerning D(r, v, K_t), where K_t, is the complete graph on t vertices, are also given.     

Accretion centers: A generalization of branch weight centroids

An ordered n-tuple (v_i1,v_i2,…,v_in) is called a sequential labelling of graph G if {v_i1,v_i2,…,v_in} = V(G) and the subgraph induced by {v_i1,v_i2,…, v_ij} is connected for 1≤j≤n. Let σ(v;G) denote the number of sequential labellings of G with v_i1=v. Vertex v is defined to be an accretion center of G if σ is maximized at v. This is shown to generalize the concept of a branch weight centroid of a tree since a vertex in a tree is an accretion center if and only if it is a centroid vertex. It is not, however, a generalization of the concept of a median since for a general graph an accretion center is not necessarily a vertex of minimum distance. A method for computing σ(v;G) based upon edge contractions is described.