TITLE

A NOTE ON PATH DOMINATION

AUTHOR(S)
ALCÓN, LILIANA
PUB. DATE
October 2016
SOURCE
Discussiones Mathematicae: Graph Theory;2016, Vol. 36 Issue 4, p1021
SOURCE TYPE
Academic Journal
DOC. TYPE
Article
ABSTRACT
We study domination between different types of walks connecting two non-adjacent vertices u and v of a graph (shortest paths, induced paths, paths, tolled walks). We succeeded in characterizing those graphs in which every uv-walk of one particular kind dominates every uv-walk of other specific kind. We thereby obtained new characterizations of standard graph classes like chordal, interval and superfragile graphs.
ACCESSION #
119119918

 

Related Articles

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

  • Majority Domatic Number - I. Manora, J. Joseline; Swaminathan, V. // Global Journal of Pure & Applied Mathematics;2010, Vol. 6 Issue 3, p275 

    In any democratic set up, the party which has majority of seats is given the opportunity to rule the state. To model such instances, the concept majority domination is introduced. This chapter deals with partitioning the vertex set into as many disjoint subsets, each being a majority dominating...

  • Domination Number of Graphs Without Small Cycles. Chen, Xue-gang; Sohn, Moo // Graphs & Combinatorics;Nov2011, Vol. 27 Issue 6, p821 

    It has been shown (J. Harant and D. Rautenbach, Domination in bipartite graphs. Discrete Math. 309:113-122, ) that the domination number of a graph of order n and minimum degree at least 2 that does not contain cycles of length 4, 5, 7, 10 nor 13 is at most $${\frac{3n}{8}}$$. They believed that...

  • Total Dominator Colorings in Paths. Vijayalekshmi, A. // International Journal of Mathematical Combinatorics;Apr2012, Vol. 2, p89 

    Let G be a graph without isolated vertices. A total dominator coloring of a graph G is a proper coloring of the graph G with the extra property that every vertex in the graph G properly dominates a color class. The smallest number of colors for which there exists a total dominator coloring of G...

  • PAIRED DOMINATION IN PRISMS OF GRAPHS. MYNHARDT, CHRISTINA M.; SCHURCH, MARK // Discussiones Mathematicae: Graph Theory;2011, Vol. 31 Issue 1, p5 

    No abstract available.

  • A CHARACTERIZATION OF LOCATING-TOTAL DOMINATION EDGE CRITICAL GRAPHS. BLIDIA, MOSTAFA; DALI, WIDAD // Discussiones Mathematicae: Graph Theory;2011, Vol. 31 Issue 1, p197 

    No abstract available.

  • Upper Singed Domination Number of Graphs. Walikar, H. B.; Motammanavar, Satish V.; Venkatesh, T. // International Journal of Mathematical Combinatorics;Mar2014, Vol. 1, p87 

    A function f : V (G) → {-1, 1} defined on the vertices of a graph G is a signed dominating function (SDF) if f(N[v]) ⩾ 1, ∀ v ϵ V , where N[v] is the closed neighborhood of v. A SDF f is minimal if there does not exists signed dominating function g, g ≠ f such that...

  • Paired-Domination in Claw-Free Graphs. Huang, Shenwei; Kang, Liying; Shan, Erfang // Graphs & Combinatorics;Nov2013, Vol. 29 Issue 6, p1777 

    A paired-dominating set of a graph G is a dominating set of vertices whose induced subgraph has a perfect matching, while the paired-domination number, denoted by γ( G), is the minimum cardinality of a paired-dominating set in G. In this paper we investigate the paired-domination number in...

  • DOWNHILL DOMINATION IN GRAPHS. HAYNES, TERESA W.; HEDETNIEMI, STEPHEN T.; JAMIESON, JESSIE D.; JAMIESON, WILLIAM B. // Discussiones Mathematicae: Graph Theory;2014, Vol. 34 Issue 3, p603 

    A path π = (v1, v2, . . ., vk+1) in a graph G = (V,E) is a downhill path if for every i, 1 ≤ i ≤ k, deg(vi) ≥ deg(vi+1), where deg(vi) denotes the degree of vertex vi ∈ V. The downhill domination number equals the minimum cardinality of a set S ⊆ V having the...

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