Geodesic
A Note on Path Domination
Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 4, pp. 1021-1034.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: domination, paths, geodesics, chordal graphs, interval graphs 
@article{DMGT_2016_36_4_a17,
     author = {Alc\'on, Liliana},
     title = {A {Note} on {Path} {Domination}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1021--1034},
     publisher = {mathdoc},
     volume = {36},
     number = {4},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a17/}
}
TY  - JOUR
AU  - Alcón, Liliana
TI  - A Note on Path Domination
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2016
SP  - 1021
EP  - 1034
VL  - 36
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a17/
LA  - en
ID  - DMGT_2016_36_4_a17
ER  - 
%0 Journal Article
%A Alcón, Liliana
%T A Note on Path Domination
%J Discussiones Mathematicae. Graph Theory
%D 2016
%P 1021-1034
%V 36
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a17/
%G en
%F DMGT_2016_36_4_a17
Alcón, Liliana. A Note on Path Domination. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 4, pp. 1021-1034. http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a17/

[1] L. Alcón, B. Brešar, T. Gologranc, M. Gutierrez, T. Kraner Šumenjak, I. Peterin and A. Tepeh, Toll convexity, European J. Combin. 46 (2015) 161-175. doi: 10.1016/j.ejc.2015.01.002

[2] A. Brandstädt, V.B. Le and J.P. Spinrad, Graph Classes: A Survey (SIAM, Monographs on Discrete Mathematics and Applications, Philadelphia, 1999). doi: 10.1137/1.9780898719796

[3] M. Changat, S. Klavžar and H.M. Mulder, The all-paths transit function of a graph, Czechoslovak Math. J. 51 (2001) 439-448. doi: 10.1023/A:1013715518448

[4] M. Changat and J. Mathew, On triangle path convexity in graphs, Discrete Math. 206 (1999) 91-95. doi: 10.1016/S0012-365X(98)00394-X

[5] M. Changat, G.N. Prasanth and I.M. Pelayo, The longest path transit function of a graph and betweenness, Util. Math. 82 (2010) 111-127.

[6] E. Howorka, A characterization of distance-hereditary graphs, Q. J. Math. 28 (1977) 417-420. doi: 10.1093/qmath/28.4.417

[7] E. Howorka, A characterization of ptolemaic graphs, J. Graph Theory 5 (1981) 323-331. doi: 10.1002/jgt.3190050314

[8] C.G. Lekkerkerker and J.Ch. Boland, Representation of a finite graph by a set of intervals on the real line, Fund. Math. 51 (1962) 45-64.

[9] T.A. McKee and F.R. McMorris, Topics in Intersection Graph Theory (SIAM, Monographs on Discrete Mathematics and Applications, Philadelphia, 1999). doi: 10.1137/1.9780898719802

[10] H.M. Mulder, Transit functions on graphs (and posets), in: M. Changat, S. Klavžar, H.M. Mulder, A. Vijayakumar, (Ed(s)), Convexity in Discrete Structures, Ramanujan Math. Soc. Lect. Notes Ser. 5 (2008) 117-130.

[11] H.M. Mulder, The Interval Function of a Graph (Mathematisch Centrum, Amsterdam, 1980).

[12] L. Nebeský, A characterization of the interval function of a connected graph, Czechoslovak Math. J. 44 (1994) 173-178.

[13] L. Nebeský, Characterizing the interval function of a connected graph, Math. Bohem. 123 (1998) 137-144.

[14] I.M. Pelayo, Geodesic Convexity in Graphs (Springer, New York, Heidelberg, Dordrecht, London, 2013). doi: 10.1007/978-1-4614-8699-2

[15] M. Preissmann, D. de Werra and N.V.R. Mahadev, A note on superbrittle graphs, Discrete Math. 61 (1986) 259-267. doi: 10.1016/0012-365X(86)90097-X

[16] J.P. Spinrad, Efficient Graph Representation, Fields Institute Monographs 19 (American Mathematics Society, Providence, 2003).

[17] D.B.West, Introduction to Graph Theory (2nd Edition, Prentice-Hall, Upper Saddle River, 2000).