Abstract | ||
---|---|---|
An ( i , j , k ) -path is a path on three vertices u , v and w in this order with d e g ( u ) ¿ i , d e g ( v ) ¿ j , and d e g ( w ) ¿ k . In this paper, we prove that every connected plane graph of girth 4 and minimum degree at least 2 has at least one of the following: a ( 2 , ∞ , 2 ) -path, a ( 2 , 7 , 3 ) -path, a ( 3 , 5 , 3 ) -path, a ( 4 , 2 , 5 ) -path, or a ( 4 , 3 , 4 ) -path. Moreover, no parameter of this description can be improved. Our result supplements recent results concerning the existence of specific 3-paths in plane graphs. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1016/j.disc.2015.04.011 | Discrete Mathematics |
Keywords | Field | DocType |
Plane graph,Structural property,Girth,3-path | Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Induced path,Distance,Structural property,Planar graph,Mathematics,Path graph | Journal |
Volume | Issue | ISSN |
338 | 9 | 0012-365X |
Citations | PageRank | References |
6 | 0.49 | 10 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Stanislav Jendrol' | 1 | 283 | 38.72 |
M. Maceková | 2 | 12 | 2.70 |
Roman Soták | 3 | 128 | 24.06 |