Search

A k -container of G between u and v , C ( u , v ) , is a set of k internally disjoint paths between u and v . A k ∗ -container C ( u , v ) of G is a k -container if it contains all vertices of G . A graph G is k ∗ -connected if there exists a k ∗ -container between any two distinct vertices. Thus, every 1 ∗ -connected graph is Hamiltonian connected. Moreover, every 2 ∗ -connected graph is Hamiltonian. Zhan proved that G = L ( M ) is Hamiltonian connected if the edge-connectivity of M is at least 4. In this paper, we generalize this result by proving G = L ( M ) is k ∗ -connected if the edge-connectivity of M is at least max { 2 k , 4 } . We also generalize our result into spanning fan-connectivity.

For a (molecular) graph, the first Zagreb index M 1 is equal to the sum of squares of the vertex degrees, and the second Zagreb index M 2 is equal to the sum of the products of degrees of pairs of adjacent vertices. In this paper, we study the Zagreb indices of graphs of order n with κ ( G ) ≤ k (resp. κ ′ ( G ) ≤ k ) and sharp lower and upper bounds are obtained for M 1 ( G ) and M 2 ( G ) for G ∈ V n k (resp. E n k ), where V n k is the set of graphs of order n with κ ( G ) ≤ k ≤ n − 1 , and E n k is the set of graphs of order n with κ ′ ( G ) ≤ k ≤ n − 1 .

In this work we show that among all n -vertex graphs with edge or vertex connectivity k , the graph G = K k ∨ ( K 1 + K n − k − 1 ) , the join of K k , the complete graph on k vertices, with the disjoint union of K 1 and K n − k − 1 , is the unique graph with maximum sum of squares of vertex degrees. This graph is also the unique n -vertex graph with edge or vertex connectivity k whose hyper-Wiener index is minimum.

A connected hypergraph H has a tree structure, i.e., H is a hypertree, if the removal of any edge from H results a disconnected hypergraph. The structure of hypertrees is described and its cycles are classified. Conditions satisfied by the dual and the transversal of hypertrees are defined and the conformality of hypertrees is described.