Path-Neighborhood Graphs

R.C. Laskar; Henry Martyn Mulder

Discussiones Mathematicae Graph Theory (2013)

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

Abstract

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

How to cite

top

R.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. [1] R. Balakrishnan, Triangle graphs, in: Graph Connections (Cochin, 1998), p. 44, Allied Publ., New Delhi, 1999. 
  2. [2] R. Balakrishnan, J. Bagga, R. Sampathkumar and N. Thillaigovindan, Triangle graphs, preprint. 
  3. [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. [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. [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. [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. [7] M. Brown and R. Connelly, On graphs with constant link II, Discrete Math. 11 (1975) 199-232.[Crossref] Zbl0304.05102
  8. [8] M. Brown and R. Connelly, Extremal problems for local properties of graphs, Australas. J. Combin. 4 (1991) 25-31. 
  9. [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. [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. [11] Y. Egawa and R.E. Ramos, Triangle graphs, Math. Japon. 36 (1991) 465-467. Zbl0743.05060
  12. [12] D. Fronček, Locally linear graphs, Math. Slovaca 39 (1989) 3-6. Zbl0664.05054
  13. [13] D. Fronček, On graphs with prescribed edge neighbourhoods, Comment. Math. Univ. Carolin. 30 (1989) 749-754. Zbl0691.05041
  14. [14] D. Fronček, Locally path-like graphs, Časopis Pĕst. Mat. 114 (1989) 176-180. Zbl0681.05043
  15. [15] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Ann. Discrete Math. 57 (Elsevier, Amsterdam, 2004). Zbl1050.05002
  16. [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. [17] F. Harary, Graph Theory (Addison-Wesley, Reading Massachusetts, 1969). 
  18. [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. [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. [20] K. Kuratowski, Sur le probl´eme des courbes gauches en topologie, Fund. Math. 15 (1930) 271-283. Zbl56.1141.03
  21. [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. [22] R.C. Laskar and H.M. Mulder, Triangle graphs, EI-Report EI 2009-42, Econometrisch Instituut, Erasmus Universiteit, Rotterdam. 
  23. [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. [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. [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. [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. [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. [28] N. Pullman, Clique covering of graphs IV. Algorithms, SIAM J. Comput. 13 (1984) 57-75. doi:10.1137/0213005[Crossref] Zbl0548.05050
  29. [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. [30] B. Zelinka, Edge neighbourhood graphs. Czechoslovak Math. J. 36 (1986) 44-47. Zbl0599.05054
  31. [31] B. Zelinka, Locally snake-like graphs, Math. Slovaka 38 (1988) 85-88. Zbl0641.05031
  32. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.