On cycles in regular 3-partite tournaments

A $c$-partite tournament is an orientation of a complete $c$-partite graph. In 2006, Volkmann conjectured that every arc of a regular 3-partite tournament $D$ is contained in an $m$-, $(m+1)$- or $(m+2)$-cycle for each $m\in \{3,4,\dots ,\left|V\left(D\right)\right|?2\}$, and this conjecture was proved to be correct for $3\le m\le 7$. In 2012, Xu et al. conjectured that every arc of an $r$-regular 3-partite tournament $D$ with $r\ge 2$ is contained in a $(3k?1)$- or $3k$-cycle for $k=2,3,\dots ,r$. They proved that this conjecture is true for $k=2$. In this paper, we confirm this conjecture for $k=3$, which also implies that Volkmann’s conjecture is correct for $m=7,8$.     

Kings and serfs in oriented graphs

In this paper, we extend the concept of kings and serfs in tournaments to that of weak kings and weak serfs in oriented graphs. We obtain various results on the existence of weak kings (weak serfs) in oriented graphs, and show the existence of n-oriented graphs containing exactly k weak kings (weak serfs), 1 ≤ k ≤ n. Also, we give the existence of n-oriented graphs containing exactly k weak kings and exactly s weak serfs such that b weak kings from k are also weak serfs.      

Cycles through 4 vertices in 3-connected graphs

S.C. Locke proposed a question: If G is a 3-connected graph with minimum degree d and X is a set of 4 vertices on a cycle in G, must G have a cycle through X with length at least min{2d,|V(G)|}? In this paper, we answer this question.     

On imbalances in oriented tripartite graphs

An oriented tripartite graph is the result of assigning a direction to each edge of a simple tripartite graph. For any vertex x in an oriented tripartite graph D(U,V,W), let d _x ⁺ and d _x ⁻ denote the outdegree and indegree respectively of x. Define $ a_{u_i } = d_{u_i }^ + - d_{u_i }^ - , b_{v_j } = d_{v_j }^ + - d_{v_j }^ - $ a_{u_i } = d_{u_i }^ + - d_{u_i }^ - , b_{v_j } = d_{v_j }^ + - d_{v_j }^ - and $ c_{w_k } = d_{w_k }^ + - d_{w_k }^ - $ c_{w_k } = d_{w_k }^ + - d_{w_k }^ - as the imbalances of the vertices u _i in U, v _j in V and w _k in W respectively. In this paper, we obtain criteria for sequences of integers to be the imbalances of some oriented tripartite graph.     

Maximum independent sets in 3- and 4-regular Hamiltonian graphs

Smooth 4-regular Hamiltonian graphs are generalizations of cycle-plus-triangles graphs. While the latter have been shown to be 3-choosable, 3-colorability of the former is NP-complete. In this paper we first show that the independent set problem for 3-regular Hamiltonian planar graphs is NP-complete, and using this result we show that this problem is also NP-complete for smooth 4-regular Hamiltonian graphs. We also show that this problem remains NP-complete if we restrict the problem to the existence of large independent sets (i.e., independent sets whose size is at least one third of the order of the graphs).     

Independent sets of maximal size in tensor powers of vertex‐transitive graphs

Let G be a connected, nonbipartite vertex‐transitive graph. We prove that if the only independent sets of maximal cardinality in the tensor product G × G are the preimages of the independent sets of maximal cardinality in G under projections, then the same holds for all finite tensor powers of G, thus providing an affirmative answer to a question raised by Larose and Tardif (J Graph Theory 40(3) (2002), 162–171). © 2009 Wiley Periodicals, Inc. J Graph Theory 60: 295‐301, 2009     

Factor-critical property in 3-dominating-critical graphs

A vertex subset S of a graph G is a dominating set if every vertex of G either belongs to S or is adjacent to a vertex of S. The cardinality of a smallest dominating set is called the dominating number of G and is denoted by γ(G). A graph G is said to be γ-vertex-critical if γ(G−v)<γ(G), for every vertex v in G.Let G be a 2-connected K_1,5-free 3-vertex-critical graph of odd order. For any vertex v∈V(G), we show that G−v has a perfect matching (except two graphs), which solves a conjecture posed by Ananchuen and Plummer [N. Ananchuen, M.D. Plummer, Matchings in 3-vertex critical graphs: The odd case, Discrete Math., 307 (2007) 1651-1658].