Maximum non-path-connected graphs

DOI10.1016/0095-8956(84)90063-7MaRDI QIDQ792336zbMATH OpenOpenAlexFDO

Authors George R. T. Hendry

Publication date 1984

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0095-8956(84)90063-7

zbMATH Keywords

path of given lengthpath-connectivity

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Connectivity (05C40)

Review text

Let n and i be integers with \(n\geq 4\) and 2\(\leq i\leq n-1\). \textit{M. Lewin} [J. Comb. Theory, Ser. B 25, 245-257 (1978; Zbl 0328.05124)] has determined the smallest size of a connected n-graph without end-vertices which ensures the existence of a path of length i between every pair of distinct vertices of the graph. This paper determines all the connected n-graphs without end-vertices of maximum size which fail to have a path of length i between every pair of distinct vertices.

Recommendations

• Connected graphs without long paths
• Various length paths in graphs
• scientific article; zbMATH DE number 4021183
• Maximum graphs not spannable by \(r\) disjoint paths
• Long path connectivity of regular graphs

Cites work

• Hamilton connected graphs
• scientific article; zbMATH DE number 3825850 (Why is no real title available?)
• scientific article; zbMATH DE number 3747163 (Why is no real title available?)
• scientific article; zbMATH DE number 3625415 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• Minimum number of edges in graphs that are both \(P_ 2-\) and \(P_ i- \)connected
• On path connected graphs
• Theory of path length distributions. I

Cited in

(3)

• Maximum graphs not spannable by \(r\) disjoint paths
• scientific article; zbMATH DE number 5942207 (Why is no real title available?)
• Maximal buttonings of non-tree graphs

This page was built for publication: Maximum non-path-connected graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q792336)