Let G be a graph and let f be a positive integer-valued function on V(G). In this paper, we show that if for all S⊆V(G), ω(G∖S)<∑v∈S(f(v)−2)+2+ω(GS), then G has a spanning tree T containing an ...arbitrary given matching such that for each vertex v, dT(v)≤f(v), where ω(G∖S) denotes the number of components of G∖S and ω(GS) denotes the number of components of the induced subgraph GS with the vertex set S. This is an improvement of several results. Next, we prove that if for all S⊆V(G), ω(G∖S)≤∑v∈S(f(v)−1)+1, then G admits a spanning closed walk passing through the edges of an arbitrary given matching meeting each vertex v at most f(v) times. This result solves a long-standing conjecture due to Jackson and Wormald (1990).
Let Cv(k; T) be the number of closed walks of length k starting at vertex v in a tree T. We prove that for any tree T with a given degree sequence π, the vector C(k; T) ≡ (Cv(k; T), v ∈ V(T)) is ...weakly majorized by the vector C(k;Tπ*)≡(Cv(k;Tπ*),v∈V(Tπ*)), where Tπ* is the greedy tree with the degree sequence π. In addition, for two trees degree sequences π and π′, if π is majorized by π′, then C(k;Tπ*) is weakly majorized by C(k;Tπ′*).
Shifting paths to avoidable ones Gurvich, Vladimir; Krnc, Matjaž; Milanič, Martin ...
Journal of graph theory,
20/May , Volume:
100, Issue:
1
Journal Article
Peer reviewed
Open access
An extension of an induced path
P in a graph
G is an induced path
P
′ such that deleting the endpoints of
P
′ results in
P. An induced path in a graph is said to be avoidable if each of its ...extensions is contained in an induced cycle. In 2019, Beisegel, Chudovsky, Gurvich, Milanič, and Servatius conjectured that every graph that contains an induced
k‐vertex path also contains an avoidable induced path of the same length, and proved the result for
k
=
2. The case
k
=
1 was known much earlier, due to a work of Ohtsuki, Cheung, and Fujisawa in 1976. The conjecture was proved for all
k in 2020 by Bonamy, Defrain, Hatzel, and Thiebaut. In the present paper, using a similar approach, we strengthen their result from a reconfiguration point of view. Namely, we show that in every graph, each induced path can be transformed to an avoidable one by a sequence of shifts, where two induced
k‐vertex paths are shifts of each other if their union is an induced path with
k
+
1 vertices. We also obtain analogous results for not necessarily induced paths and for walks. In contrast, the statement cannot be extended to trails or to isometric paths.
On extremal bipartite bicyclic graphs Huang, Jing; Li, Shuchao; Zhao, Qin
Journal of mathematical analysis and applications,
04/2016, Volume:
436, Issue:
2
Journal Article
Peer reviewed
Open access
Let Bn+ be the set of all connected bipartite bicyclic graphs with n vertices. The Estrada index of a graph G is defined as EE(G)=∑i=1neλi, where λ1,λ2,…,λn are the eigenvalues of the adjacency ...matrix of G, and the Kirchhoff index of a graph G is defined as Kf(G)=∑i<jrij, where rij is the resistance distance between vertices vi and vj in G. The complement of G is denoted by G‾. In this paper, sharp upper bound on EE(G) (resp. Kf(G‾)) of graph G in Bn+ is established. The corresponding extremal graphs are determined, respectively. Furthermore, by means of some newly created inequalities, the graph G in Bn+ with the second maximal EE(G) (resp. Kf(G‾)) is identified as well. It is interesting to see that the first two bicyclic graphs in Bn+ according to these two orderings are mainly coincident.
On a poset of trees revisited Li, Shuchao; Yu, Yuantian
Advances in applied mathematics,
June 2021, 2021-06-00, Volume:
127
Journal Article
Peer reviewed
This contribution gives an extensive study on the Wiener indices, the number of closed walks, the coefficients of some graph polynomials (the adjacency polynomial, the Laplacian polynomial, the edge ...cover polynomial and the independence polynomial) of trees. Csikvári (2010) 4 introduced the generalized tree shift, which keeps the number of vertices of trees. Applying the generalized tree shifts and recurrence relation, we extend the works of Csikvári (2010) 4 and Csikvári (2013) 5. Using a unified approach, we obtain the following main results: Firstly, for all n and ℓ, we characterize the unique tree having the maximum (resp. minimum) Wiener index and the unique tree having the maximum (resp. minimum) number of closed walks of length ℓ among the trees of order n which are neither a path nor a star. Secondly, we characterize the unique tree whose adjacency polynomial (resp. Laplacian polynomial, independence polynomial) has the maximum (resp. minimum) coefficients in absolute value among the trees of order n which are neither a path nor a star, respectively. At last, we identify all the n-vertex trees whose edge cover polynomial has the minimum coefficients in absolute value and we also determine the unique tree having the maximum coefficients in absolute value among the trees of order n which are neither a path nor a star.
Let Un+ be the set of connected bipartite unicyclic graphs with n vertices. Here we consider the extremal graphs in Un+ with respect to both the Estrada index of themselves and the Kirchhoff index of ...their complements. We find that the first two and the last one unicyclic graphs in Un+ according to these two orderings are coincident.
Acyclicity in edge-colored graphs Gutin, Gregory; Jones, Mark; Sheng, Bin ...
Discrete mathematics,
02/2017, Volume:
340, Issue:
2
Journal Article
Peer reviewed
Open access
A walk W in edge-colored graphs is called properly colored (PC) if every pair of consecutive edges in W is of different color. We introduce and study five types of PC acyclicity in edge-colored ...graphs such that graphs of PC acyclicity of type i is a proper superset of graphs of acyclicity of type i+1, i=1,2,3,4. The first three types are equivalent to the absence of PC cycles, PC closed trails, and PC closed walks, respectively. While graphs of types 1, 2 and 3 can be recognized in polynomial time, the problem of recognizing graphs of type 4 is, somewhat surprisingly, NP-hard even for 2-edge-colored graphs (i.e., when only two colors are used). The same problem with respect to type 5 is polynomial-time solvable for all edge-colored graphs. Using the five types, we investigate the border between intractability and tractability for the problems of finding the maximum number of internally vertex-disjoint PC paths between two vertices and the minimum number of vertices to meet all PC paths between two vertices.
The Kirchhoff index of a graph G is defined as Kf(G)=12∑i=1n∑j=1nrij, where rij is the resistance distance between vi and vj. Let G be a simple bipartite graph, G¯ the complement graph of G. First, ...we get an expression for Kf(G¯) in terms of the numbers of closed walks of subdivision graph of G. Then, as an application, we determine the trees with the first and second maximum and minimum values of Kf(T¯).
We present the transformation of several sums of positive integer powers of the sine and cosine into non-trigonometric combinatorial forms. The results are applied to the derivation of generating ...functions and to the number of the closed walks on a path and in a cycle.
PDF
