Minimum number of edges in graphs that are both P2- and Pi-connected

✍ Scribed by Yoko Usami

• Publisher: Elsevier Science
• Year: 1983
• Tongue: English
• Weight: 473 KB
• Volume: 44
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(83)90060-2

✦ Synopsis

A simple graph with n vertices is called Pi-connected if any two distinct vertices are connected by an elementary path of length i. In this paper, lower bounds of the number of edges in graphs that are both Pz-and Pi-connected are obtained. Namely if i ~j(n + I), then JE(G)I 3((4i -5)1(2i -2))(n -11, and if i >i(n + l), then jE(G)i 3 2(n -1) apart from one exceptional graph. Furthermore, extremal graphs are determined in the former.

1. Intruductiun

In this paper, we shall consider finite undirected simple graphs. The set of vertices (resp. the set of edges) of a graph G is denoted by V(G) (resp. E(G)). A path of length i which does not pass through a vertex more than once is referred to as an i-path. When there is an i-path conneciing two vertices u and U, we shall say that the property Pi(U, t>) holds. A graph G is called Pi-connected if Pi(u, tr) holds for any two distinct vertices U, u in V(G). Set 1 V(G)( = n. R.J. Faudree, C.C. Rousseau and R.H. Schelp [l] determined the minimum number of edges in graphs that are both &-and P,,_,-connected, and showed that the wheel graph W,, is the unique extremal graph. Note that W,, is &-connected for all i (2<jdn--1).

Let Lk denote a graph consisting of a path (linear tree) of length k -1. Kk is a complete graph with k vertices, H, + I-I2 is the join graph of a graph f-I, and a graph Hz, and ntN is the union graph of m copies of a graph f$ (cfi [Z]).

This paper is devoted to the proof of the following theorem.