On the minimum number of components in a cotree of a graph
As a generalization of the Sierpiński-like graphs, the subdivided-line graph Г(G) of a simple connected graph G is defined to be the line graph of the barycentric subdivision of G. In this paper we obtain a closed-form formula for the enumeration of spanning trees in Г(G), employing the theory of electrical networks. We present bounds for the largest and second smallest Laplacian eigenvalues of Г(G) in terms of the maximum degree, the number of edges, and the first Zagreb index of G. In addition,...
H. Kheddouci, J.F. Saclé and M. Woźniak conjectured in 2000 that if a tree T is not a star, then there is an edge-disjoint placement of T into its third power.In this paper, we prove the conjecture for caterpillars.
Let be the adjacency matrix of . The characteristic polynomial of the adjacency matrix is called the characteristic polynomial of the graph and is denoted by or simply . The spectrum of consists of the roots (together with their multiplicities) of the equation . The largest root is referred to as the spectral radius of . A -shape is a tree with exactly two of its vertices having maximal degree 4. We will denote by
Let G be a graph and C be a set of cycles of G. The tree graph of G defined by C, is the graph T(G,C) that has one vertex for each spanning tree of G, in which two trees T and T' are adjacent if their symmetric difference consists of two edges and the unique cycle contained in T ∪ T' is an element of C. We give a necessary and sufficient condition for this graph to be connected for the case where every edge of G belongs to at most two cycles in C.
For any two positive integers and , let be a digraph whose set of vertices is and such that there is a directed edge from a vertex to a vertex if . Let be the prime factorization of . Let be the set of all primes dividing and let be such that and . A fundamental constituent of , denoted by , is a subdigraph of induced on the set of vertices which are multiples of and are relatively prime to all primes . L. Somer and M. Křížek proved that the trees attached to all cycle...