The connectivity of total graphs

Source abstract

We associate with a graph (finite, undirected, without loops and multiple lines) a graph T ( G ), called the total graph of G . This new graph has the property that a one-to-one correspondence can be established between its points and the elements (points and lines) of G such that two points of T(G) are adjacent if and only if the corresponding elements of G are adjacent or incident. The object of this article is to prove the following theorem: If K(G 1 ) = n, n ≥ 1, and λ(G2) = m, m ≥ 1 , then K(T(G 1 )) ≥ n + 2 + [(n - 2)/3], λ( T (G 1 )) ≥ 2n , K ( T(G 2 )) ≥ m + 1, and λ( T(G 2 )) ≥ 2m , where k ( G ) and λ( G ) denote the connectivity and line-connectivity of the graph G .