An integer k-matching of a graph G is a function h:E(G)→{0,1,…,k} such that ∑e∈Γ(v)h(e)≤k for any v∈V(G), where Γ(v) is the set of edges incident to v. The integer k-matching number of G, denoted by ...mk(G), is the maximum number of ∑e∈E(G)h(e) over all integer k-matching h of G. In this paper, we establish the following lower bounds on the sum of the integer k-matching number of a graph G and its complement by using Gallai–Edmonds Structure Theorem: (1) mk(G)+mk(G¯)≥⌊nk2⌋ for n≥2;
(2) if G and G¯ are non-empty, then for n≥25, mk(G)+mk(G¯)≥⌊nk+k2⌋;
(3) if G and G¯ have no isolated vertices, then for n≥25, mk(G)+mk(G¯)≥⌊nk2⌋+2k . Furthermore, all extremal graphs attaining the lower bounds are also characterized.
The k‐th power of a graph G, denoted by Gk, is a graph with the same set of vertices as G such that two vertices are adjacent in Gk if and only if their distance in G is at most k. In this paper, we ...give the bounds on the spectral radius of Tk and Gk(k≥1). The Nordhaus–Gaddum‐type inequality for the spectral radius of the graph Gk is also presented. Moreover, we obtain an upper bound on the energy of the second power of graphs.
The fractional matching number of a graph G, written as α′(G), is the maximum size of a fractional matching of G. The following sharp lower bounds for a graph G of order n are proved, and all ...extremal graphs are characterized in this paper.
(1) α′(G)+α′(G¯)≥n2 for n≥2.
(2) If G and G¯ are non-empty, then for n≥30, α′(G)+α′(G¯)≥n+12.
(3) If G and G¯ have no isolated vertices, then for n≥30, α′(G)+α′(G¯)≥n+42.
The Wiener polarity index W sub(p)(G) of a graph G is the number of unordered pairs of vertices {u, v} in G such that the distance between u and v is equal to 3. Very recently, Zhang and Hu studied ...the Wiener polarity index in Y. Zhang, Y. Hu, 2016 38. In this short paper, we establish an upper bound on the Wiener polarity index in terms of Hosoya index and characterize the corresponding extremal graphs. Moreover, we obtain Nordhaus-Gaddum-type results for W sub(p)(G ). Our lower bound on View the MathML source Wp(G)+Wp(Gmacr) is always better than the previous lower bound given by Zhang and Hu.
Let k≥2 be an integer, a k-decomposition(G1,G2,…,Gk) of the complete graph Kn is a partition of its edge set to form k spanning subgraphs G1,G2,…,Gk. In this contribution, we investigate the ...Nordhaus–Gaddum-type inequality of a k-decomposition of Kn for the general Zagreb index and a 2-decomposition for the Zagreb co-indices, respectively. The corresponding extremal graphs are characterized.
Let k≥2 be an integer, a k-decomposition(G1,G2,⋯,Gk) of a graph G is a partition of its edge set to form k spanning subgraphs G1,G2,…,Gk. The hyper-Wiener index WW is one of the recently conceived ...distance-based graph invariants (Randi 1993 15): WW=WW(G):=12W(G)+12W2(G), where W is the Wiener index (Wiener 1947 18) and W2 is the sum of squares of distance of all pairs of vertices in G. In this paper, we investigate the Nordhaus–Gaddum-type inequality of a 3-decomposition of Kn for the hyper-Wiener index: 7n2≤WW(G1)+WW(G2)+WW(G3)≤2n+24+n2+4(n−1). The corresponding extremal graphs are characterized.
PDF
