A note on the existence of edges in the (1, 2)-step competition graph of a round digraph.
Xinhong Zhang, Ruijuan Li, Shengjia Li, Gaokui Xu · Australas. J Comb. · 2013
Factor and Merz [Discrete Appl. Math. 159 (2011), 100–103] defined the (1, 2)-step competition graph and studied the (1, 2)-step competition graph of a tournament. In this paper, a sufficient and necessary condition for any two vertices to be adjacent in the (1, 2)-step competition graph C1,2(D) of a round digraph D is given. 1 Terminology and Introduction The competition graph of a digraph, introduced by Cohen to study “food web” models in 1968, has been extensively studied in connection to some biological models and some radio communication networks. For a comprehensive introduction to competition graphs, see [3, 11, 12]. Recent work in competition graph theory includes [8, 10]. In 1991, Hefner (Factor) et al. defined the (i, j) competition graph in [7]. In 2008, Hedetniemi et al. [6] introduced (1, 2)-domination. This was followed by Factor and Langley’s introduction of the (1, 2)-domination graph in [4]. Because of the similarities in construction, the (1, 2)-step competition graph was defined by Factor and Merz in 2011. In [5], they completely characterized the (1, 2)-step competition graphs of tournaments and extended the results to the (i, k)-step competition graphs. ∗ Also at: Department of Applied Mathematics, Taiyuan University of Science and Technology, 030024 Taiyuan, P.R. China. † Corresponding author: [email protected]. Research is partially supported by the Youth Foundation of Shanxi Province (2013021001–5) and Shanxi Scholarship Council of China (2013– 017). ‡ Research is partially supported by the National Natural Science Foundation of China (61174082). 288 X. ZHANG, R. LI, S. LI AND G. XU It will be assumed that the reader is familiar with the concepts of graphs and digraphs. The other untouched terminology can be found in [1]. Let D be a digraph on n vertices. Then V (D) and A(D) denote its vertex and arc sets, respectively. If (x, y) is an arc of D, then we say that x dominates y and sometimes use the notation x → y to denote this arc. The outset of a vertex x ∈ V (D) is the set N(x) = {y | (x, y) ∈ A(D)}. Similarly, N−(x) = {y | (y, x) ∈ A(D)} is the inset of x. The numbers d(x) = |N+(x)| and d−(x) = |N−(x)| are called the outdegree and indegree of x, respectively (if necessary, we write d+D(x) and d − D(x) instead of d(x) and d−(x), respectively). Let H be a subgraph of D. If every arc of A(D), which has both vertices in V (H), is in A(H), we say that H is induced by X = V (H) (we write H = D[X]) and call H an induced subdigraph of D. In addition, D −X = D[V (D)−X] for any X ⊆ V (D). Cycles and paths are always simple and directed. An arc (x, y) of a digraph D is ordinary if (y, x) is not in D. A cycle Q of a digraph D is ordinary if all arcs of Q are ordinary. If x and y are vertices of D then the distance from x to y in D, denoted dD(x, y) = d(x, y), is the minimum length of an (x, y)-path, if y is reachable from x, and otherwise d(x, y) = ∞. Let G be a graph. The vertex and edge sets are denoted by V (G) and E(G) respectively. Recall that the competition graph of a digraph of D is obtained by using vertex set V (D) and adding edge xy whenever N(x) ∩ N(y) = ∅. The (1, 2)-step competition graph of a digraph D, denoted C1,2(D), is a graph on V (D) where xy ∈ E(C1,2(D)) if and only if there exists a vertex z = x, y, such that either dD−y(x, z) = 1 and dD−x(y, z) ≤ 2 or dD−x(y, z) = 1 and dD−y(x, z) ≤ 2. A digraph on n vertices is called a round digraph if we can label its vertices v0, v1, . . . , vn−1 such that for each i, N(vi) = {vi+1, . . . , vi+d+(vi)} and N−(vi) = {vi−d−(vi), . . . , vi−1}, where the subscripts are taken modulo n. We will refer to the ordering v0, v1, . . . , vn−1 as a round labelling of D. For example, a round digraph on 5 vertices and its (1, 2)-step competition graph are shown in Fig. 1. A digraph D is strong if every vertex of D is reachable by a directed path from every other vertex of D. A strong component of a digraph D is a maximal induced subdigraph of D which is strong. If D1, D2, . . . , Dt are the strong components of D, then we call V (D1), V (D2), . . . , V (Dt) the strong decomposition ofD. The underlying EXISTENCE OF EDGES 289 graph of D, denoted by UG(D), is the graph obtained by ignoring the orientations of arcs in D and deleting parallel edges. We say that D is connected if its underlying graph is connected. In this paper, we only consider connected digraphs. A digraph D is semicomplete if, for any pair of vertices x, y ∈ V (D), either (x, y) ∈ A(D), or (y, x) ∈ A(D), or both, i.e., UG(D) is complete. A tournament is a semicomplete digraph without a cycle of length 2. A digraph D is locally semicomplete if D[N(x)] and D[N−(x)] are both semicomplete for every vertex x of D. A digraph D is transitive if, for every pair of arcs (x, y) and (y, z) in D such that x = z, the arc (x, z) is also in D. It is easy to show that a tournament is transitive if and only if it is acyclic. Proposition 1.1 (Huang [9]) Every round digraph is locally semicomplete. Theorem 1.2 (Huang [9]) A connected locally semicomplete digraph D is round if and only if the following holds for each vertex x of D: (a) N(x) −N−(x) and N−(x) −N+(x) induce transitive tournaments; and (b) N(x) ∩ N−(x) induces a (semicomplete) subdigraph containing no ordinary cycle. Theorem 1.3 (Bang-Jensen [2]) Every strong locally semicomplete digraph is hamiltonian.