Combinatorial proofs of some determinantal identities

In this paper, we give combinatorial proofs of some determinantal identities. In fact, we give a combinatorial proof of a theorem of R. P. Stanley regarding the enumeration of paths in acyclic digraphs along with some interesting applications. We also give an almost visual proof of a recent result of Oliver Knill, namely ‘The generalized Cauchy–Binet Theorem.’     

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

顺序和顺序哈密顿有向图

A digraph D is k-ordered if for every sequence S:v 1,v 2,…,v k of k distinct vertices,there exists a cycle C such that C encounters the vertices of S in the specified order.In particular,we say that D is k-ordered hamiltonian if for every sequence S:v 1,v 2,…,v k of k distinct vertices,there exists a hamiltonian cycle C such that the vertices of S are encountered on C in the specified order.In this paper,sufficient conditions for digraphs to be ordered and ordered hamiltonian have been given.     

A note on an embedding problem in transitive tournaments

Let TT_n be a transitive tournament on n vertices. It is known Görlich, Pil?niak, Wo?niak, (2006) [3] that for any acyclic oriented graph of order n and size not greater than , two graphs isomorphic to are arc-disjoint subgraphs of TT_n. In this paper, we consider the problem of embedding of acyclic oriented graphs into their complements in transitive tournaments. We show that any acyclic oriented graph of size at most is embeddable into all its complements in TT_n. Moreover, this bound is generally the best possible.     

Spanning 2-strong tournaments in 3-strong semicomplete digraphs

We prove that every 3-strong semicomplete digraph on at least 5 vertices contains a spanning 2-strong tournament. Our proof is constructive and implies a polynomial algorithm for finding a spanning 2-strong tournament in a given 3-strong semicomplete digraph. We also show that there are infinitely many (2k−2)-strong semicomplete digraphs which contain no spanning k-strong tournament and conjecture that every(2k−1)-strong semicomplete digraph which is not the complete digraph on 2k vertices contains a spanning k-strong tournament.     

Graphs and digraphs with all 2-factors isomorphic

We show that a digraph which contains a directed 2-factor and has minimum in-degree and out-degree at least four has two non-isomorphic directed 2-factors. As a corollary, we deduce that every graph which contains a 2-factor and has minimum degree at least eight has two non-isomorphic 2-factors. In addition we construct: an infinite family of 3-diregular digraphs with the property that all their directed 2-factors are Hamilton cycles, an infinite family of 2-connected 4-regular graphs with the property that all their 2-factors are isomorphic, and an infinite family of cyclically 6-edge-connected cubic graphs with the property that all their 2-factors are Hamilton cycles.     

几个著名网络的限长路径

设给出了（h,ψ）-η限长路径问题是图论中的Menger定理的变形和推广，在实时容错网络设计和分析中有重要意义。对于给定的正整数d,Ad(D)表示网络D中任何距离至少为2的两顶点之间内点不交且长度都不超过d的路的最大条数；Bd(D)表示D的顶点子集B中的最小顶点数使得D－B的直径大于d.已证明确定Ad(D)的问题是NPC问题，而且显然有不等式Ad(D)≤Bd(D)。本文考虑D为超立方体网络、De Bruijn网络和Kautz网络，对d的不同值确定了Ad(D)及Bd(D),而且均有Ad(D)=Bd(D)。     

Note on Perfect Forests in Digraphs

A spanning subgraph F of a graph G is called perfect if F is a forest, the degree of each vertex x in F is odd, and each tree of F is an induced subgraph of G. Alex Scott (Graphs Combin 17 (2001), 539–553) proved that every connected graph G contains a perfect forest if and only if G has an even number of vertices. We consider four generalizations to directed graphs of the concept of a perfect forest. While the problem of existence of the most straightforward one is NP‐hard, for the three others this problem is polynomial‐time solvable. Moreover, every digraph with only one strong component contains a directed forest of each of these three generalization types. One of our results extends Scott's theorem to digraphs in a nontrivial way.