Given a simple graph G and a positive integer k, the induced matching k-partition problem asks whether there exists a k-partition (V 1, V 2, ..., V k) of V(G) such that for each i(1≤i≤k), G[V i] is 1-regular. This p...Given a simple graph G and a positive integer k, the induced matching k-partition problem asks whether there exists a k-partition (V 1, V 2, ..., V k) of V(G) such that for each i(1≤i≤k), G[V i] is 1-regular. This paper studies the computational complexity of this problem for graphs with small diameters. The main results are as follows: Induced matching 2-partition problem of graphs with diameter 6 and induced matching 3-partition problem of graphs with diameter 2 are NP-complete; induced matching 2-partition problem of graphs with diameter 2 is polynomially solvable.展开更多
A(3,6)-fullerene is a connected cubic plane graph whose faces are only triangles and hexagons,and has the connectivity 2 or 3.The(3,6)-fullerenes with connectivity 2 are the tubes consisting of l concentric hexagonal ...A(3,6)-fullerene is a connected cubic plane graph whose faces are only triangles and hexagons,and has the connectivity 2 or 3.The(3,6)-fullerenes with connectivity 2 are the tubes consisting of l concentric hexagonal layers such that each layer consists of two hexangons,capped on each end by two adjacent triangles,denoted by T_(l)(l≥1).A(3,6)-fullerene Tl with n vertices has exactly 2n/4+1 perfect matchings.The structure of a(3,6)-fullerene G with connectivity 3 can be determined by only three parameters r,s and t,thus we denote it by G=(r,s,t),where r is the radius(number of rings),s is the size(number of spokes in each layer,s(≥4,s is even),and t is the torsion(0≤t<s,t≡r mod 2).In this paper,the counting formula of the perfect matchings in G=n+1,4,t)is given,and the number of perfect matchpings is obtained.Therefore,the correctness of the conclusion that every bridgeless cubic graph with p vertices has at least 2p/3656perfect matchings proposed by Esperet et al is verified for(3,6)-fullerene G=(n+1,4,t).展开更多
Enumeration of perfect matchings on graphs has a longstanding interest in combinatorial mathematics. In this paper, we obtain some explicit expressions of the number of perfect matchings for a type of Archimedean latt...Enumeration of perfect matchings on graphs has a longstanding interest in combinatorial mathematics. In this paper, we obtain some explicit expressions of the number of perfect matchings for a type of Archimedean lattices with toroidal boundary by applying Tesler's crossing orientations to obtain some Pfaffan orientations and enumerating their Pfaffans.展开更多
Let I with |I| = k be a matching of a graph G (briefly, I is called a k-matching). If I is not a proper subset of any other matching of G, then I is a maximal k-matching and m(gk, G) is used to denote the number of ma...Let I with |I| = k be a matching of a graph G (briefly, I is called a k-matching). If I is not a proper subset of any other matching of G, then I is a maximal k-matching and m(gk, G) is used to denote the number of maximal k-matchings of G. Let gk be a k-matching of G, if there exists a subset {e1, e2,…, ei} of E(G) \ gk, i (?)1, such that (1) for any j ∈ {1, 2,…,i}, gk + {ej} is a (k + l)-matching of G; (2) for any f ∈ E(G) \ (gk ∪ {e1,e2,…,ei}), gk + {f} is not a matching of G; then gk, is called an i wings k-matching of G and mi(gk,G) is used to denote the number of i wings k-matchings of G. In this paper, it is proved that both mi(gk,G) and m(gk,G) are edge reconstructible for every connected graph G, and as a corollary, it is shown that the matching polynomial is edge reconstructible.展开更多
The induced matching cover number of a graph G without isolated vertices, denoted by imc(G),is the minimum integer k such that G has k induced matchings {M1,M2,···,Mk}such that,V(M1)∪V(M2)∪··...The induced matching cover number of a graph G without isolated vertices, denoted by imc(G),is the minimum integer k such that G has k induced matchings {M1,M2,···,Mk}such that,V(M1)∪V(M2)∪···∪V(Mk)covers V(G).This paper shows that,if G is a 3-regular claw-free graph,then imc(G)∈{2,3}.展开更多
In 2012, Gutman and Wagner proposed the concept of the matching energy of a graph and pointed out that its chemical applications can go back to the 1970s. The matching energy of a graph is defined as the sum of the ab...In 2012, Gutman and Wagner proposed the concept of the matching energy of a graph and pointed out that its chemical applications can go back to the 1970s. The matching energy of a graph is defined as the sum of the absolute values of the zeros of its matching polynomial. Let u and v be the non-isolated vertices of the graphs G and H with the same order, respectively. Let wi?be a non-isolated vertex of graph Gi?where i=1, 2, …, k. We use Gu(k)?(respectively, Hv(k)) to denote the graph which is the coalescence of G (respectively, H) and G1, G2,…, Gk?by identifying the vertices u (respectively, v) and w1, w2,…, wk. In this paper, we first present a new technique of directly comparing the matching energies of Gu(k)?and Hv(k), which can tackle some quasi-order incomparable problems. As the applications of the technique, then we can determine the unicyclic graphs with perfect matchings of order 2n with the first to the ninth smallest matching energies for all n≥211.展开更多
This article extend the John E. Hopcroft and Richart M. Karp Algorithm (HK Algorithm) for maximum matchings in bipartite graphs to the non-bipartite case by providing a new approach to deal with the blossom in alterna...This article extend the John E. Hopcroft and Richart M. Karp Algorithm (HK Algorithm) for maximum matchings in bipartite graphs to the non-bipartite case by providing a new approach to deal with the blossom in alternating paths in the process of searching for augmenting paths, which different from well-known “shrinking” way of Edmonds and makes the algorithm for maximum matchings in general graphs more simple.展开更多
Let G be a properly colored bipartite graph. A rainbow matching of G is such a matching in which no two edges have the same color. Let G be a properly colored bipartite graph with bipartition (X,Y) and . We show that ...Let G be a properly colored bipartite graph. A rainbow matching of G is such a matching in which no two edges have the same color. Let G be a properly colored bipartite graph with bipartition (X,Y) and . We show that if , then G has a rainbow coloring of size at least .展开更多
Let k be a positive integer and G a bipartite graph with bipartition (X,Y). A perfect 1-k matching is an edge subset M of G such that each vertex in Y is incident with exactly one edge in M and each vertex in X is inc...Let k be a positive integer and G a bipartite graph with bipartition (X,Y). A perfect 1-k matching is an edge subset M of G such that each vertex in Y is incident with exactly one edge in M and each vertex in X is incident with exactly k edges in M. A perfect 1-k matching is an optimal semi-matching related to the load-balancing problem, where a semi-matching is an edge subset M such that each vertex in Y is incident with exactly one edge in M, and a vertex in X can be incident with an arbitrary number of edges in M. In this paper, we give three sufficient and necessary conditions for the existence of perfect 1-k matchings and for the existence of 1-k matchings covering | X |−dvertices in X, respectively, and characterize k-elementary bipartite graph which is a graph such that the subgraph induced by all k-allowed edges is connected, where an edge is k-allowed if it is contained in a perfect 1-k matching.展开更多
Artificial intelligence(AI)is increasingly recognized as a transformative force in the field of solid organ transplantation.From enhancing donor-recipient matching to predicting clinical risks and tailoring immunosupp...Artificial intelligence(AI)is increasingly recognized as a transformative force in the field of solid organ transplantation.From enhancing donor-recipient matching to predicting clinical risks and tailoring immunosuppressive therapy,AI has the potential to improve both operational efficiency and patient outcomes.Despite these advancements,the perspectives of transplant professionals-those at the forefront of critical decision-making-remain insufficiently explored.To address this gap,this study utilizes a multi-round electronic Delphi approach to gather and analyses insights from global experts involved in organ transplantation.Participants are invited to complete structured surveys capturing demographic data,professional roles,institutional practices,and prior exposure to AI technologies.The survey also explores perceptions of AI’s potential benefits.Quantitative responses are analyzed using descriptive statistics,while open-ended qualitative responses undergo thematic analysis.Preliminary findings indicate a generally positive outlook on AI’s role in enhancing transplantation processes,particularly in areas such as donor matching and post-operative care.These mixed views reflect both optimism and caution among professionals tasked with integrating new technologies into high-stakes clinical workflows.By capturing a wide range of expert opinions,the findings will inform future policy development,regulatory considerations,and institutional readiness frameworks for the integration of AI into organ transplantation.展开更多
We consider the problem of existence of a Hamiltonian cycle containing a matching and avoiding some edges in an n-cubc Qn,and obtain the following results.Let n≥3,MСE(Qn),and FСE(Qn)\M with 1≤|F|≤2n-4-|M|.If M is...We consider the problem of existence of a Hamiltonian cycle containing a matching and avoiding some edges in an n-cubc Qn,and obtain the following results.Let n≥3,MСE(Qn),and FСE(Qn)\M with 1≤|F|≤2n-4-|M|.If M is a matching and every vertex is incident with at least two edges in the graph Qn-F,then all edges of M lie on a Hamiltonian cycle in Qn-F.Moreover,if|M|=1 or|M|==2,then the upper bound of number of faulty edges tolerated is sharp.Our results generalize the well-known result for |M|=1.展开更多
Let G be a simple graph. Define R(G) to be the graph obtained from G by adding a new vertex e* corresponding to each edge e = (a, b) of G and by joining each new vertex e* to the end vertices a and b of the edge e cor...Let G be a simple graph. Define R(G) to be the graph obtained from G by adding a new vertex e* corresponding to each edge e = (a, b) of G and by joining each new vertex e* to the end vertices a and b of the edge e corresponding to it. In this paper, we prove that the number of matchings of R(G) is completely determined by the degree sequence of vertices of G.展开更多
This paper studies,under substitutable and cardinal monotone preferences,the lattice structure of the set SePT of many-to-many pairwise-stable matchings.It proves that the selection matchings are increasing functions ...This paper studies,under substitutable and cardinal monotone preferences,the lattice structure of the set SePT of many-to-many pairwise-stable matchings.It proves that the selection matchings are increasing functions on SePT.This fact,along with a few auxiliary results,is then used to prove that SePT is a distributive lattice.The contribution of this paper is not new,but the alternative proof is interesting as it avoids the use of abstract lattice theory.展开更多
Let G be a properly edge-colored graph. A rainbow matching of G is a matching in which no two edges have the same color. Let 5 denote the minimum degree of G. We show that if Iv（G）I 〉 （σ2 ＋ 14σ ＋ 1）/4, then G...Let G be a properly edge-colored graph. A rainbow matching of G is a matching in which no two edges have the same color. Let 5 denote the minimum degree of G. We show that if Iv（G）I 〉 （σ2 ＋ 14σ ＋ 1）/4, then G has a rainbow matching of size 6, which answers a question asked by G. Wang [Electron. J. Combin., 2011, 18： #N162] affirmatively. In addition, we prove that if G is a properly colored bipartite graph with bipartition （X, Y） and max{lXl, IYI} 〉 （σ2 ＋ 4σ - 4）/4, then G has a rainbow matching of size σ.展开更多
Let ：T2k＋1 be the set of trees on 2k＋ 1 vertices with nearly perfect matchings, and let S2k＋2 be the set of trees on 2k ＋ 2 vertices with perfect matchings. The largest Laplacian spectral radii of trees in ：T2k...Let ：T2k＋1 be the set of trees on 2k＋ 1 vertices with nearly perfect matchings, and let S2k＋2 be the set of trees on 2k ＋ 2 vertices with perfect matchings. The largest Laplacian spectral radii of trees in ：T2k＋l and S2k＋2 and the corresponding trees were given by Guo （2003）. In this paper, the authors determine the second to the sixth largest Laplacian spectral radii among all trees in T2k＋1 and give the corresponding trees.展开更多
Let G be a simple graph with order n. The eigenvalues of G are defined as the eigenvalues of its adjacent matrix A（G）. Now A（G） is a real symmetric square matrix, so all the eigenvalues of G are real, and can be o...Let G be a simple graph with order n. The eigenvalues of G are defined as the eigenvalues of its adjacent matrix A（G）. Now A（G） is a real symmetric square matrix, so all the eigenvalues of G are real, and can be ordered as λ<sub>1</sub>（G）≥λ<sub>2</sub>（G）≥…≥λ<sub>n</sub>（G）. If G is bipartite, then λ<sub>i</sub> （G）=-λ<sub>n-i+1</sub> （G） （1≤i≤[n/2]）. The eigenvalues of a bipartite graph have physics meanings in the study of quantum chemistry, so it is of certain significance展开更多
Let φ（G）, κ（G）, α（G）, χ（G）, cl（G）, diam（G） denote the number of perfect matchings, connectivity, independence number, chromatic number, clique number and diameter of a graph G, respectively. In this no...Let φ（G）, κ（G）, α（G）, χ（G）, cl（G）, diam（G） denote the number of perfect matchings, connectivity, independence number, chromatic number, clique number and diameter of a graph G, respectively. In this note, by constructing some extremal graphs, the following extremal problems are solved： 1. max {φ（G）： ｜V（G）｜ = 2n, κ（G）≤ k} = k[（2n - 3）!!], 2. max{φ（G）： ｜V（G）｜ = 2n,α（G） ≥ k} =[∏ i=0^k-1 （2n - k-i]（2n - 2k - 1）!!], 3. max{φ（G）： ｜V（G）｜=2n, χ（G） ≤ k} =φ（Tk,2n） Tk,2n is the Turán graph, that is a complete k-partitc graph on 2n vertices in which all parts are as equal in size as possible, 4. max{φ（G）： ｜V（G）｜ = 2n, cl（G） = 2} = n!, 5. max{φ（G）： ｜V（G）｜ = 2n, diam（G） ≥〉 2} = （2n - 2）（2n - 3）[（2n - 5）!!], max{φ（G）： ｜V（G）｜ = 2n, diam（G） ≥ 3} = （n - 1）^2[（2n - 5）!!].展开更多
A matching M of a graph G is an induced matching if no two edges in M arejoined by an edge of G.Let iz(G) denote the total number of induced matchings of G,named iz-index.It is well known that the Hosoya index of a gr...A matching M of a graph G is an induced matching if no two edges in M arejoined by an edge of G.Let iz(G) denote the total number of induced matchings of G,named iz-index.It is well known that the Hosoya index of a graph is the total number of matchings and the Hosoya index of a path can be calculated by the Fibonacci sequence.In this paper,we investigate the iz-index of graphs by using the Fibonacci-Narayana sequence and characterize some types of graphs with minimum and maximum iz-index,respectively.展开更多
Let T_(2k+1)be the set of trees on 2k+1 vertices with nearly perfect matchings andα(T)be the algebraic connectivity of a tree T.The authors determine the largest twelve values of the algebraic connectivity of the tre...Let T_(2k+1)be the set of trees on 2k+1 vertices with nearly perfect matchings andα(T)be the algebraic connectivity of a tree T.The authors determine the largest twelve values of the algebraic connectivity of the trees in T_(2k+1).Specifically,10 trees T_(2),T_(3),...,T11 and two classes of trees T(1)and T(12)in T_(2k+1)are introduced.It is shown in this paper that for each tree T′_(1),T′_(11)∈T(1)and T^′_(12),T′_(11)2∈T(12)and each i,j with 2≤i〈j≤11,α(T′_(1))=α(T′_(11))〉α(Tj)〉α(T^′_(12))=α(T′_(11)2).It is also shown that for each tree T with T∈T_(2k+1)/(T(1)∪{T_(2),T_(3),…,T11}∪T(12)),α(T^′_(12))〉α(T).展开更多
基金Supported by the National Natural Science Foundation of China( 1 0 371 1 1 2 ) and the Natural ScienceFoundation of Henan( 0 4 1 1 0 1 1 2 0 0 )
文摘Given a simple graph G and a positive integer k, the induced matching k-partition problem asks whether there exists a k-partition (V 1, V 2, ..., V k) of V(G) such that for each i(1≤i≤k), G[V i] is 1-regular. This paper studies the computational complexity of this problem for graphs with small diameters. The main results are as follows: Induced matching 2-partition problem of graphs with diameter 6 and induced matching 3-partition problem of graphs with diameter 2 are NP-complete; induced matching 2-partition problem of graphs with diameter 2 is polynomially solvable.
基金Supported by National Natural Science Foundation of China(11801148,11801149 and 11626089)the Foundation for the Doctor of Henan Polytechnic University(B2014-060)
文摘A(3,6)-fullerene is a connected cubic plane graph whose faces are only triangles and hexagons,and has the connectivity 2 or 3.The(3,6)-fullerenes with connectivity 2 are the tubes consisting of l concentric hexagonal layers such that each layer consists of two hexangons,capped on each end by two adjacent triangles,denoted by T_(l)(l≥1).A(3,6)-fullerene Tl with n vertices has exactly 2n/4+1 perfect matchings.The structure of a(3,6)-fullerene G with connectivity 3 can be determined by only three parameters r,s and t,thus we denote it by G=(r,s,t),where r is the radius(number of rings),s is the size(number of spokes in each layer,s(≥4,s is even),and t is the torsion(0≤t<s,t≡r mod 2).In this paper,the counting formula of the perfect matchings in G=n+1,4,t)is given,and the number of perfect matchpings is obtained.Therefore,the correctness of the conclusion that every bridgeless cubic graph with p vertices has at least 2p/3656perfect matchings proposed by Esperet et al is verified for(3,6)-fullerene G=(n+1,4,t).
基金Supported by the National Natural Science Foundation of China(Grant No.11471273 11671186)
文摘Enumeration of perfect matchings on graphs has a longstanding interest in combinatorial mathematics. In this paper, we obtain some explicit expressions of the number of perfect matchings for a type of Archimedean lattices with toroidal boundary by applying Tesler's crossing orientations to obtain some Pfaffan orientations and enumerating their Pfaffans.
基金Research supported partially by NSFC (10001035) and(10371055)
文摘Let I with |I| = k be a matching of a graph G (briefly, I is called a k-matching). If I is not a proper subset of any other matching of G, then I is a maximal k-matching and m(gk, G) is used to denote the number of maximal k-matchings of G. Let gk be a k-matching of G, if there exists a subset {e1, e2,…, ei} of E(G) \ gk, i (?)1, such that (1) for any j ∈ {1, 2,…,i}, gk + {ej} is a (k + l)-matching of G; (2) for any f ∈ E(G) \ (gk ∪ {e1,e2,…,ei}), gk + {f} is not a matching of G; then gk, is called an i wings k-matching of G and mi(gk,G) is used to denote the number of i wings k-matchings of G. In this paper, it is proved that both mi(gk,G) and m(gk,G) are edge reconstructible for every connected graph G, and as a corollary, it is shown that the matching polynomial is edge reconstructible.
基金Supported by the National Natural Science Foundation of China（10771179）
文摘The induced matching cover number of a graph G without isolated vertices, denoted by imc(G),is the minimum integer k such that G has k induced matchings {M1,M2,···,Mk}such that,V(M1)∪V(M2)∪···∪V(Mk)covers V(G).This paper shows that,if G is a 3-regular claw-free graph,then imc(G)∈{2,3}.
文摘In 2012, Gutman and Wagner proposed the concept of the matching energy of a graph and pointed out that its chemical applications can go back to the 1970s. The matching energy of a graph is defined as the sum of the absolute values of the zeros of its matching polynomial. Let u and v be the non-isolated vertices of the graphs G and H with the same order, respectively. Let wi?be a non-isolated vertex of graph Gi?where i=1, 2, …, k. We use Gu(k)?(respectively, Hv(k)) to denote the graph which is the coalescence of G (respectively, H) and G1, G2,…, Gk?by identifying the vertices u (respectively, v) and w1, w2,…, wk. In this paper, we first present a new technique of directly comparing the matching energies of Gu(k)?and Hv(k), which can tackle some quasi-order incomparable problems. As the applications of the technique, then we can determine the unicyclic graphs with perfect matchings of order 2n with the first to the ninth smallest matching energies for all n≥211.
文摘This article extend the John E. Hopcroft and Richart M. Karp Algorithm (HK Algorithm) for maximum matchings in bipartite graphs to the non-bipartite case by providing a new approach to deal with the blossom in alternating paths in the process of searching for augmenting paths, which different from well-known “shrinking” way of Edmonds and makes the algorithm for maximum matchings in general graphs more simple.
文摘Let G be a properly colored bipartite graph. A rainbow matching of G is such a matching in which no two edges have the same color. Let G be a properly colored bipartite graph with bipartition (X,Y) and . We show that if , then G has a rainbow coloring of size at least .
文摘Let k be a positive integer and G a bipartite graph with bipartition (X,Y). A perfect 1-k matching is an edge subset M of G such that each vertex in Y is incident with exactly one edge in M and each vertex in X is incident with exactly k edges in M. A perfect 1-k matching is an optimal semi-matching related to the load-balancing problem, where a semi-matching is an edge subset M such that each vertex in Y is incident with exactly one edge in M, and a vertex in X can be incident with an arbitrary number of edges in M. In this paper, we give three sufficient and necessary conditions for the existence of perfect 1-k matchings and for the existence of 1-k matchings covering | X |−dvertices in X, respectively, and characterize k-elementary bipartite graph which is a graph such that the subgraph induced by all k-allowed edges is connected, where an edge is k-allowed if it is contained in a perfect 1-k matching.
文摘Artificial intelligence(AI)is increasingly recognized as a transformative force in the field of solid organ transplantation.From enhancing donor-recipient matching to predicting clinical risks and tailoring immunosuppressive therapy,AI has the potential to improve both operational efficiency and patient outcomes.Despite these advancements,the perspectives of transplant professionals-those at the forefront of critical decision-making-remain insufficiently explored.To address this gap,this study utilizes a multi-round electronic Delphi approach to gather and analyses insights from global experts involved in organ transplantation.Participants are invited to complete structured surveys capturing demographic data,professional roles,institutional practices,and prior exposure to AI technologies.The survey also explores perceptions of AI’s potential benefits.Quantitative responses are analyzed using descriptive statistics,while open-ended qualitative responses undergo thematic analysis.Preliminary findings indicate a generally positive outlook on AI’s role in enhancing transplantation processes,particularly in areas such as donor matching and post-operative care.These mixed views reflect both optimism and caution among professionals tasked with integrating new technologies into high-stakes clinical workflows.By capturing a wide range of expert opinions,the findings will inform future policy development,regulatory considerations,and institutional readiness frameworks for the integration of AI into organ transplantation.
基金The work was supported by the National Natural Science Foundation of China(Grant No.11401290).
文摘We consider the problem of existence of a Hamiltonian cycle containing a matching and avoiding some edges in an n-cubc Qn,and obtain the following results.Let n≥3,MСE(Qn),and FСE(Qn)\M with 1≤|F|≤2n-4-|M|.If M is a matching and every vertex is incident with at least two edges in the graph Qn-F,then all edges of M lie on a Hamiltonian cycle in Qn-F.Moreover,if|M|=1 or|M|==2,then the upper bound of number of faulty edges tolerated is sharp.Our results generalize the well-known result for |M|=1.
文摘Let G be a simple graph. Define R(G) to be the graph obtained from G by adding a new vertex e* corresponding to each edge e = (a, b) of G and by joining each new vertex e* to the end vertices a and b of the edge e corresponding to it. In this paper, we prove that the number of matchings of R(G) is completely determined by the degree sequence of vertices of G.
文摘This paper studies,under substitutable and cardinal monotone preferences,the lattice structure of the set SePT of many-to-many pairwise-stable matchings.It proves that the selection matchings are increasing functions on SePT.This fact,along with a few auxiliary results,is then used to prove that SePT is a distributive lattice.The contribution of this paper is not new,but the alternative proof is interesting as it avoids the use of abstract lattice theory.
文摘Let G be a properly edge-colored graph. A rainbow matching of G is a matching in which no two edges have the same color. Let 5 denote the minimum degree of G. We show that if Iv（G）I 〉 （σ2 ＋ 14σ ＋ 1）/4, then G has a rainbow matching of size 6, which answers a question asked by G. Wang [Electron. J. Combin., 2011, 18： #N162] affirmatively. In addition, we prove that if G is a properly colored bipartite graph with bipartition （X, Y） and max{lXl, IYI} 〉 （σ2 ＋ 4σ - 4）/4, then G has a rainbow matching of size σ.
基金supported by the National Natural Science Foundation of China under Grant No. 10331020.
文摘Let ：T2k＋1 be the set of trees on 2k＋ 1 vertices with nearly perfect matchings, and let S2k＋2 be the set of trees on 2k ＋ 2 vertices with perfect matchings. The largest Laplacian spectral radii of trees in ：T2k＋l and S2k＋2 and the corresponding trees were given by Guo （2003）. In this paper, the authors determine the second to the sixth largest Laplacian spectral radii among all trees in T2k＋1 and give the corresponding trees.
基金Project supported by the National Natural Science Foundation of China.
文摘Let G be a simple graph with order n. The eigenvalues of G are defined as the eigenvalues of its adjacent matrix A（G）. Now A（G） is a real symmetric square matrix, so all the eigenvalues of G are real, and can be ordered as λ<sub>1</sub>（G）≥λ<sub>2</sub>（G）≥…≥λ<sub>n</sub>（G）. If G is bipartite, then λ<sub>i</sub> （G）=-λ<sub>n-i+1</sub> （G） （1≤i≤[n/2]）. The eigenvalues of a bipartite graph have physics meanings in the study of quantum chemistry, so it is of certain significance
基金Supported by the National Natural Science Foundation of China(No.10331020)
文摘Let φ（G）, κ（G）, α（G）, χ（G）, cl（G）, diam（G） denote the number of perfect matchings, connectivity, independence number, chromatic number, clique number and diameter of a graph G, respectively. In this note, by constructing some extremal graphs, the following extremal problems are solved： 1. max {φ（G）： ｜V（G）｜ = 2n, κ（G）≤ k} = k[（2n - 3）!!], 2. max{φ（G）： ｜V（G）｜ = 2n,α（G） ≥ k} =[∏ i=0^k-1 （2n - k-i]（2n - 2k - 1）!!], 3. max{φ（G）： ｜V（G）｜=2n, χ（G） ≤ k} =φ（Tk,2n） Tk,2n is the Turán graph, that is a complete k-partitc graph on 2n vertices in which all parts are as equal in size as possible, 4. max{φ（G）： ｜V（G）｜ = 2n, cl（G） = 2} = n!, 5. max{φ（G）： ｜V（G）｜ = 2n, diam（G） ≥〉 2} = （2n - 2）（2n - 3）[（2n - 5）!!], max{φ（G）： ｜V（G）｜ = 2n, diam（G） ≥ 3} = （n - 1）^2[（2n - 5）!!].
基金supported by the Science and Technology Program of Guangzhou,China (No.202002030183)by the Qinghai Province Natural Science Foundation (No.2020-ZJ-924)by the Guangdong Province Natural Science Foundationauthorized in 2020。
文摘A matching M of a graph G is an induced matching if no two edges in M arejoined by an edge of G.Let iz(G) denote the total number of induced matchings of G,named iz-index.It is well known that the Hosoya index of a graph is the total number of matchings and the Hosoya index of a path can be calculated by the Fibonacci sequence.In this paper,we investigate the iz-index of graphs by using the Fibonacci-Narayana sequence and characterize some types of graphs with minimum and maximum iz-index,respectively.
文摘Let T_(2k+1)be the set of trees on 2k+1 vertices with nearly perfect matchings andα(T)be the algebraic connectivity of a tree T.The authors determine the largest twelve values of the algebraic connectivity of the trees in T_(2k+1).Specifically,10 trees T_(2),T_(3),...,T11 and two classes of trees T(1)and T(12)in T_(2k+1)are introduced.It is shown in this paper that for each tree T′_(1),T′_(11)∈T(1)and T^′_(12),T′_(11)2∈T(12)and each i,j with 2≤i〈j≤11,α(T′_(1))=α(T′_(11))〉α(Tj)〉α(T^′_(12))=α(T′_(11)2).It is also shown that for each tree T with T∈T_(2k+1)/(T(1)∪{T_(2),T_(3),…,T11}∪T(12)),α(T^′_(12))〉α(T).
