# Path-Neighborhood Graphs

R.C. Laskar; Henry Martyn Mulder

Discussiones Mathematicae Graph Theory (2013)

- Volume: 33, Issue: 4, page 731-745
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topR.C. Laskar, and Henry Martyn Mulder. "Path-Neighborhood Graphs." Discussiones Mathematicae Graph Theory 33.4 (2013): 731-745. <http://eudml.org/doc/268278>.

@article{R2013,

abstract = {A path-neighborhood graph is a connected graph in which every neighborhood induces a path. In the main results the 3-sun-free path-neighborhood graphs are characterized. The 3-sun is obtained from a 6-cycle by adding three chords between the three pairs of vertices at distance 2. A Pk-graph is a path-neighborhood graph in which every neighborhood is a Pk, where Pk is the path on k vertices. The Pk-graphs are characterized for k ≤ 4.},

author = {R.C. Laskar, Henry Martyn Mulder},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {path-neighborhood graph; outerplanar graph; MOP; snake; 3- sun; k-fun; 3-sun; -fun},

language = {eng},

number = {4},

pages = {731-745},

title = {Path-Neighborhood Graphs},

url = {http://eudml.org/doc/268278},

volume = {33},

year = {2013},

}

TY - JOUR

AU - R.C. Laskar

AU - Henry Martyn Mulder

TI - Path-Neighborhood Graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2013

VL - 33

IS - 4

SP - 731

EP - 745

AB - A path-neighborhood graph is a connected graph in which every neighborhood induces a path. In the main results the 3-sun-free path-neighborhood graphs are characterized. The 3-sun is obtained from a 6-cycle by adding three chords between the three pairs of vertices at distance 2. A Pk-graph is a path-neighborhood graph in which every neighborhood is a Pk, where Pk is the path on k vertices. The Pk-graphs are characterized for k ≤ 4.

LA - eng

KW - path-neighborhood graph; outerplanar graph; MOP; snake; 3- sun; k-fun; 3-sun; -fun

UR - http://eudml.org/doc/268278

ER -

## References

top- [1] R. Balakrishnan, Triangle graphs, in: Graph Connections (Cochin, 1998), p. 44, Allied Publ., New Delhi, 1999.
- [2] R. Balakrishnan, J. Bagga, R. Sampathkumar and N. Thillaigovindan, Triangle graphs, preprint.
- [3] H.J. Bandelt and H.M. Mulder, Pseudo-median graphs: decompostion via amalgamation and Cartesian multiplication, Discrete Math. 94 (1991) 161-180. doi:10.1016/0012-365X(91)90022-T[Crossref]
- [4] M. Borowiecki, P. Borowiecki, E. Sidorowicz and Z. Skupień, On extremal sizes of locally k-tree graphs, Czechoslovak Math. J. 60 (2010) 571-587. doi:10.1007/s10587-010-0037-z[Crossref] Zbl1224.05246
- [5] A. Brandstädt, V.B. Le, and J.P. Spinrad, Graph classes a survey (in: SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, 1999).
- [6] M. Brown and R. Connelly, On graphs with constant link, in: New directions in the theory of graphs, Proc. Third Ann Arbor Conf., Univ. Michigan, Ann Arbor, Mich., 1971, F. Harary Ed. (Academic Press, New York, 1973) 19-51. doi:10.1016/0012-365X(75)90037-0[Crossref]
- [7] M. Brown and R. Connelly, On graphs with constant link II, Discrete Math. 11 (1975) 199-232.[Crossref] Zbl0304.05102
- [8] M. Brown and R. Connelly, Extremal problems for local properties of graphs, Australas. J. Combin. 4 (1991) 25-31.
- [9] B.L. Chilton, R. Gould and A.D. Polimeni, A note on graphs whose neighborhoods are n-cycles, Geom. Dedicata 3 (1974) 289-294. doi:10.1007/BF00181321[Crossref] Zbl0325.05116
- [10] A.A. Diwan and N. Usharani, A condition for the three colourability of planar locally path graphs, in: Foundations of software technology and theoretical computer science (Bangalore, 1995), 52-61, Lecture Notes in Comput. Sci., 1026, Springer, Berlin, 1995. doi:10.1007/3-540-60692-0 40[Crossref]
- [11] Y. Egawa and R.E. Ramos, Triangle graphs, Math. Japon. 36 (1991) 465-467. Zbl0743.05060
- [12] D. Fronček, Locally linear graphs, Math. Slovaca 39 (1989) 3-6. Zbl0664.05054
- [13] D. Fronček, On graphs with prescribed edge neighbourhoods, Comment. Math. Univ. Carolin. 30 (1989) 749-754. Zbl0691.05041
- [14] D. Fronček, Locally path-like graphs, Časopis Pĕst. Mat. 114 (1989) 176-180. Zbl0681.05043
- [15] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Ann. Discrete Math. 57 (Elsevier, Amsterdam, 2004). Zbl1050.05002
- [16] J.I. Hall, Graphs with constnt link and small degree and order, J. Graph Theory 9 (1985) 419-444. doi:10.1002/jgt.3190090313[Crossref]
- [17] F. Harary, Graph Theory (Addison-Wesley, Reading Massachusetts, 1969).
- [18] P. Hell, Graphs with given neighborhoods I, in: Probl´emes combinatoires et th´eorie des graphes, Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976, (Colloq. Internat. CNRS, 260, CNRS, Paris, 1978) 219-223.
- [19] R.E. Jamison, F.R. McMorris and H.M. Mulder, Graphs with only caterpillars as spanning trees, Discrete Math. 272 (2003) 81-95. doi:10.1016/S0012-365X(03)00186-9[Crossref] Zbl1029.05034
- [20] K. Kuratowski, Sur le probl´eme des courbes gauches en topologie, Fund. Math. 15 (1930) 271-283. Zbl56.1141.03
- [21] R.C. Laskar, H.M. Mulder and B. Novick, Maximal outerplanar graphs as chordal graphs, as path-neighborhood graphs, and as triangle graphs, Australas. J. Combin. 52 (2012) 185-195. Zbl1248.05172
- [22] R.C. Laskar and H.M. Mulder, Triangle graphs, EI-Report EI 2009-42, Econometrisch Instituut, Erasmus Universiteit, Rotterdam.
- [23] C. Lekkerkerker and J. Boland, Representation of a graph by a finite set of intervals on the real line, Fund. Math. 51 (1962) 45-64. Zbl0105.17501
- [24] A. Márquez, A. de Mier, M. Noy and M.P. Revuelta, Locally grid graphs: classification and Tutte uniqueness, Discrete Math. 266 (2003) 327-352. doi:10.1016/S0012-365X(02)00818-X[Crossref] Zbl1032.05038
- [25] S.L. Mitchell, Algorithms on trees and maximal outerplanar graphs: design, complexity analysis and data structures study, PhD Thesis, University of Virginia, 1977.
- [26] T.D. Parsons, Circulant graphs embeddings, J. Combin. Theory (B) 29 (1980) 310-320. doi:10.1016/0095-8956(80)90088-X[Crossref]
- [27] T.D. Parsons and T. Pisanski, Graphs which are locally paths, in: Combinatorics and Graph Theory, Banach Center Publ., 25, (PWN, Warsaw, 1989) 127-135 Zbl0757.05071
- [28] N. Pullman, Clique covering of graphs IV. Algorithms, SIAM J. Comput. 13 (1984) 57-75. doi:10.1137/0213005[Crossref] Zbl0548.05050
- [29] S.M. Ulam, A collection of mathematical problems, in: Interscience Tracts in Pure and Applied Mathematics, Vol. XIII, No. 8, (Interscience Publishers, New York/London, 1960).
- [30] B. Zelinka, Edge neighbourhood graphs. Czechoslovak Math. J. 36 (1986) 44-47. Zbl0599.05054
- [31] B. Zelinka, Locally snake-like graphs, Math. Slovaka 38 (1988) 85-88. Zbl0641.05031
- [32] A.A. Zykov, Graph-theoretical results of Novosibirsk mathematicians in: M. Fiedler ed., Theory of Graphs and its Applications, Proc. Sympos. Smolenice, 1963 (Publ. House Czechoslovak Acad. Sci., Prague 1964) 151-153.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.