TITLE

On the Domination Number of Cartesian Product of Two Directed Cycles

AUTHOR(S)
Zehui Shao; Enqiang Zhu; Fangnian Lang
PUB. DATE
January 2013
SOURCE
Journal of Applied Mathematics;2013, p1
SOURCE TYPE
Academic Journal
DOC. TYPE
Article
ABSTRACT
Denote by ɣ(G) the domination number of a digraph G and CmCn the Cartesian product of Cm and Cn, the directed cycles of length m, n = 2. In 2010, Liu et al. determined the exact values of ɣ(CmCn) for m = 2, 3, 4, 5, 6. In 2013, Mollard determined the exact values of ɣ(CmCn) form = 3k+2. In this paper, we give lower and upper bounds of ɣ(CmCn) withm = 3k+1 for different cases. In particular, [(2k + 1)n/2] = ɣ(C3k+1Cn) = [(2k + 1)n/2] + k. Based on the established result, the exact values of ɣ(CmCn) are determined for m = 7 and 10 by the combination of the dynamic algorithm, and an upper bound for ɣ(C13Cn) is provided.
ACCESSION #
95250838

 

Related Articles

  • MONOCHROMATIC CYCLES AND MONOCHROMATIC PATHS IN ARC-COLORED DIGRAPHS. GALEANA-SÁNCHEZ, HORTENSIA; GAYTÁN-GÓMEZ, GUADALUPE; ROJAS-MONROY, ROCÍO // Discussiones Mathematicae: Graph Theory;2011, Vol. 31 Issue 2, p283 

    No abstract available.

  • On Sullivan's conjecture on cycles in 4-free and 5-free digraphs. Liang, Hao; Xu, Jun // Acta Mathematica Sinica;Jan2013, Vol. 29 Issue 1, p53 

    For a simple digraph G, let β( G) be the size of the smallest subset X ⊆ E( G) such that G−X has no directed cycles, and let γ( G) be the number of unordered pairs of nonadjacent vertices in G. A digraph G is called k-free if G has no directed cycles of length at most k. This...

  • A General Lower Bound for the Domination Number of Cylindrical Graphs. Carreño, José Juan; Martínez, José Antonio; Puertas, María Luz // Bulletin of the Malaysian Mathematical Sciences Society;Mar2020, Vol. 43 Issue 2, p1671 

    In this paper, we present a lower bound for the domination number of the Cartesian product of a path and a cycle that is tight if the length of the cycle is a multiple of five. This bound improves the natural lower bound obtained by using the domination number of the Cartesian product of two...

  • INDEPENDENT DETOUR TRANSVERSALS IN 3-DEFICIENT DIGRAPHS. VAN AARDT, SUSAN; FRICK, MARIETJIE; SINGLETON, JOY // Discussiones Mathematicae: Graph Theory;2013, Vol. 33 Issue 2, p261 

    In 1982 Laborde, Payan and Xuong [Independent sets and longest directed paths in digraphs, in: Graphs and other combinatorial topics (Prague, 1982) 173-177 (Teubner-Texte Math., 59 1983)] conjectured that every digraph has an independent detour transversal (IDT), i.e. an independent set which...

  • On the Extremal Number of Edges in Hamiltonian Graphs. TUNG-YANG HO; CHENG-KUAN LIN; TAN, JIMMY J. M.; HSU, D. FRANK; LIH-HSING HSU // Journal of Information Science & Engineering;Sep2011, Vol. 27 Issue 5, p1659 

    Assume that n and δ are positive integers with 2 ≤ δ < n. Let h(n, δ) be the minimum number of edges required to guarantee an n-vertex graph with minimum degree δ(G) ≥ δ to be hamiltonian, i.e., any n-vertex graph G with δ(G) ≥ δ is hamiltonian if |E(G)|...

  • Integer Functions on the Cycle Space and Edges of a Graph. Slilaty, Daniel C. // Graphs & Combinatorics;Mar2010, Vol. 26 Issue 2, p293 

    A directed graph has a natural Z-module homomorphism from the underlying graph's cycle space to Z where the image of an oriented cycle is the number of forward edges minus the number of backward edges. Such a homomorphism preserves the parity of the length of a cycle and the image of a cycle is...

  • UNDERLYING GRAPHS OF 3-QUASI-TRANSITIVE DIGRAPHS AND 3-TRANSITIVE DIGRAPHS RUIXIA WANG, SHIYING WANG. RUIXIA WANG; SHIYING WANG // Discussiones Mathematicae: Graph Theory;2013, Vol. 33 Issue 2, p429 

    A digraph is 3-quasi-transitive (resp. 3-transitive), if for any path x0x1 x2x3 of length 3, x0 and x3 are adjacent (resp. x0 dominates x3). César Hernández-Cruz conjectured that if D is a 3-quasi-transitive digraph, then the underlying graph of D, UG(D), admits a 3-transitive orientation....

  • HAMILTONIAN-COLORED POWERS OF STRONG DIGRAPHS. JOHN, GARRY; JONES, RYAN; KOLASINSKI, KYLE; ZHANG, PING // Discussiones Mathematicae: Graph Theory;2012, Vol. 32 Issue 4, p705 

    For a strong oriented graph D of order n and diameter d and an integer k with 1≤ k ≤ d, the kth power Dk of D is that digraph having vertex set V(D) with the property that (u, v) is an arc of Dk if the directed distance dD(u, v) from u to v in D is at most k. For every strong digraph...

  • ASTEROIDAL QUADRUPLES IN NON ROOTED PATH GRAPHS. GUTIERREZ, MARISA; LÉVÊQUE, BENJAMIN; TONDATO, SILVIA B. // Discussiones Mathematicae: Graph Theory;2015, Vol. 35 Issue 4, p16 

    A directed path graph is the intersection graph of a family of directed subpaths of a directed tree. A rooted path graph is the intersection graph of a family of directed subpaths of a rooted tree. Rooted path graphs are directed path graphs. Several characterizations are known for directed path...

Share

Read the Article

Courtesy of THE LIBRARY OF VIRGINIA

Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics