The products of graphs discussed in this paper are the following four kinds: the Cartesian product of graphs, the tensor product of graphs, the lexicographic product of graphs and the strong direct product of graphs. ...The products of graphs discussed in this paper are the following four kinds: the Cartesian product of graphs, the tensor product of graphs, the lexicographic product of graphs and the strong direct product of graphs. It is proved that:① If the graphs G 1 and G 2 are the connected graphs, then the Cartesian product, the lexicographic product and the strong direct product in the products of graphs, are the path positive graphs. ② If the tensor product is a path positive graph if and only if the graph G 1 and G 2 are the connected graphs, and the graph G 1 or G 2 has an odd cycle and max{ λ 1μ 1,λ nμ m}≥2 in which λ 1 and λ n [ or μ 1 and μ m] are maximum and minimum characteristic values of graph G 1 [ or G 2 ], respectively.展开更多
In this paper,we first give a sufficient condition for a graph being fractional ID-[a,b]-factor-critical covered in terms of its independence number and minimum degree,which partially answers the problem posed by Sizh...In this paper,we first give a sufficient condition for a graph being fractional ID-[a,b]-factor-critical covered in terms of its independence number and minimum degree,which partially answers the problem posed by Sizhong Zhou,Hongxia Liu and Yang Xu(2022).Then,an A_(α)-spectral condition is given to ensure that G is a fractional ID-[a,b]-factor-critical covered graph and an(a,b,k)-factor-critical graph,respectively.In fact,(a,b,k)-factor-critical graph is a graph which has an[a,b]-factor for k=0.Thus,these above results extend the results of Jia Wei and Shenggui Zhang(2023)and Ao Fan,Ruifang Liu and Guoyan Ao(2023)in some sense.展开更多
A set S of vertices of a graph G is called a decycling set if G-S is acyclic.The smallest size of a decycling set is called the decycling number of G and is denoted by ∇(G).In this paper,we investigate the decycling n...A set S of vertices of a graph G is called a decycling set if G-S is acyclic.The smallest size of a decycling set is called the decycling number of G and is denoted by ∇(G).In this paper,we investigate the decycling number of type-k Halin graphs,focusing on those that are formed from trees that have just two degrees k and 3.For any type-k Halin graph G of order n,we prove that(k-2)n+k^(2)-4k+5/(k-1)^(2)≤∇(G)≤n+k-3/k-1.The result not only supports the largest forest conjecture due to Albertson and Berman(1976),but also offers a tight lower bound for the decycling number of type-3 Halin graphs and several type-k Halin graphs.Moreover,a new formula to determine the cardinality of any decycling set S of a type-k Halin graph G is provided.展开更多
A graph has exactly two main eigenvalues if and only if it is a 2-walk linear graph.In this paper,we show some necessary conditions that a 2-walk（a,b）-linear graph must obey.Using these conditions and some basic the...A graph has exactly two main eigenvalues if and only if it is a 2-walk linear graph.In this paper,we show some necessary conditions that a 2-walk（a,b）-linear graph must obey.Using these conditions and some basic theorems in graph theory,we characterize all 2-walk linear graphs with small cyclic graphs without pendants.The results are given in sort on unicyclic,bicyclic,tricyclic graphs.展开更多
A nowhere-zero k-flow on a graph G=(V(G),E(G))is a pair(D,f),where D is an orientation on E(G)and f:E(G)→{±1,±2,,±(k-1)}is a function such that the total outflow equals to the total inflow at each vert...A nowhere-zero k-flow on a graph G=(V(G),E(G))is a pair(D,f),where D is an orientation on E(G)and f:E(G)→{±1,±2,,±(k-1)}is a function such that the total outflow equals to the total inflow at each vertex.This concept was introduced by Tutte as an extension of face colorings,and Tutte in 1954 conjectured that every bridgeless graph admits a nowhere-zero 5-flow,known as the 5-Flow Conjecture.This conjecture is verified for some graph classes and remains unresolved as of today.In this paper,we show that every bridgeless graph of Euler genus at most 20 admits a nowhere-zero 5-flow,which improves several known results.展开更多
Detecting overlapping communities in attributed networks remains a significant challenge due to the complexity of jointly modeling topological structure and node attributes,the unknown number of communities,and the ne...Detecting overlapping communities in attributed networks remains a significant challenge due to the complexity of jointly modeling topological structure and node attributes,the unknown number of communities,and the need to capture nodes with multiple memberships.To address these issues,we propose a novel framework named density peaks clustering with neutrosophic C-means.First,we construct a consensus embedding by aligning structure-based and attribute-based representations using spectral decomposition and canonical correlation analysis.Then,an improved density peaks algorithm automatically estimates the number of communities and selects initial cluster centers based on a newly designed cluster strength metric.Finally,a neutrosophic C-means algorithm refines the community assignments,modeling uncertainty and overlap explicitly.Experimental results on synthetic and real-world networks demonstrate that the proposed method achieves superior performance in terms of detection accuracy,stability,and its ability to identify overlapping structures.展开更多
Geologic time is an essential dimension in geological research,acting as a pivotal attribute that integrates data across various subdisciplines.The Geologic Time Scale(GTS)provides a formal framework for interpreting ...Geologic time is an essential dimension in geological research,acting as a pivotal attribute that integrates data across various subdisciplines.The Geologic Time Scale(GTS)provides a formal framework for interpreting and communicating geologic time within the field of geological studies,such as macro-geological evolution and regional geologic surveys.展开更多
A graph whose edges are labeled either as positive or negative is called a signed graph.Hameed et al.introduced signed distance and distance compatibility in 2021,initially to characterize balanced signed graphs which...A graph whose edges are labeled either as positive or negative is called a signed graph.Hameed et al.introduced signed distance and distance compatibility in 2021,initially to characterize balanced signed graphs which have nice spectral properties.This article mainly studies the conjecture proposed by Shijin et al.on the distance compatibility of the direct product of signed graphs,and provides necessary and sufficient conditions for the distance compatibility of the direct product of signed graphs.Some further questions regarding distance compatibility are also posed.展开更多
Let G be a graph andαÎ[0,1),Nikiforov merged the adjacency matrix and the signless Laplacian matrix to A_(α)(G)=αD(G)+(1-α)A(G),where D(G)A(G)are the degree diagonal matrix and the adjacency matrix of G,respe...Let G be a graph andαÎ[0,1),Nikiforov merged the adjacency matrix and the signless Laplacian matrix to A_(α)(G)=αD(G)+(1-α)A(G),where D(G)A(G)are the degree diagonal matrix and the adjacency matrix of G,respectively.The spectral radius of A_(α)(G)is called byα-spectral radius of the graph G.In this paper,we study the perturbation of the complete multipartite graphsα-spectral radius when move a vertex from a part to other part of the complete multipartite graphs.Moreover,we give some conditions when theα-spectral Turán of graphs implies the Turán theorem of graphs.展开更多
Recently, Furtula et al. proposed a valuable predictive index in the study of the heat of formation in octanes and heptanes, the augmented Zagreb index （AZI index） of a graph G, which is defined asAZI（G） = ∑uv∈E...Recently, Furtula et al. proposed a valuable predictive index in the study of the heat of formation in octanes and heptanes, the augmented Zagreb index （AZI index） of a graph G, which is defined asAZI（G） = ∑uv∈E（G）（dudv/du＋du-2）3,where E（G） is the edge set of G, d~ and d~ are the degrees of the terminal vertices u and v of edge uv, respectively. In this paper, we obtain the first five largest （resp., the first two smallest） AZI indices of connected graphs with n vertices. Moreover, we determine the trees of order n with the first three smallest AZI indices, the unicyclic graphs of order n with the minimum, the second minimum AZI indices, and the bicyclic graphs of order n with the minimum AZI index, respectively.展开更多
A graph G is said to be determined by its Laplacian spectrum if any graph having the same Laplacian spectrum as G is isomorphic to G.We consider θ-graphs,that is,graphs obtained by subdividing the edges of the multig...A graph G is said to be determined by its Laplacian spectrum if any graph having the same Laplacian spectrum as G is isomorphic to G.We consider θ-graphs,that is,graphs obtained by subdividing the edges of the multigraph consist of three parallel edges.In this paper,some special θ-graphs are determined by their Laplacian spectra.展开更多
In this paper,we investigate spacelike graphs defined over a domain Ω⊂M^(n) in the Lorentz manifold M^(n)×ℝ with the metric−ds^(2)+σ,where M^(n) is a complete Riemannian n-manifold with the metricσ,Ωhas piece...In this paper,we investigate spacelike graphs defined over a domain Ω⊂M^(n) in the Lorentz manifold M^(n)×ℝ with the metric−ds^(2)+σ,where M^(n) is a complete Riemannian n-manifold with the metricσ,Ωhas piecewise smooth boundary,and ℝ denotes the Euclidean 1-space.We prove an interesting stability result for translating spacelike graphs in M^(n)×ℝ under a conformal transformation.展开更多
Let j, k and m be three positive integers, a circular m-L（j, k）-labeling of a graph G is a mapping f： V（G）→{0, 1, …, m-1}such that f（u）-f（v）m≥j if u and v are adjacent, and f（u）-f（v）m≥k if u and v are...Let j, k and m be three positive integers, a circular m-L（j, k）-labeling of a graph G is a mapping f： V（G）→{0, 1, …, m-1}such that f（u）-f（v）m≥j if u and v are adjacent, and f（u）-f（v）m≥k if u and v are at distance two,where a-bm=min{a-b,m-a-b}. The minimum m such that there exists a circular m-L（j, k）-labeling of G is called the circular L（j, k）-labeling number of G and is denoted by σj, k（G）. For any two positive integers j and k with j≤k,the circular L（j, k）-labeling numbers of trees, the Cartesian product and the direct product of two complete graphs are determined.展开更多
A graph G is H-free,if it contains no H as a subgraph.A graph G is said to be H-minor free,if it does not contain H as a minor.In 2010,Nikiforov asked that what the maximum spectral radius of an H-free graph of order ...A graph G is H-free,if it contains no H as a subgraph.A graph G is said to be H-minor free,if it does not contain H as a minor.In 2010,Nikiforov asked that what the maximum spectral radius of an H-free graph of order n is.In this paper,we consider some Brualdi-Solheid-Turan type problems on bipartite graphs.In 2015,Zhai,Lin and Gong in[Linear Algebra Appl.,2015,471:21-27]proved that if G is a bipartite graph with order n≥2k+2 and ρ(G)≥ρ(K_(k,n-k)),then G contains a C_(2k+2) unless G≌K_(k,n-k).First,we give a new and more simple proof for the above theorem.Second,we prove that if G is a bipartite graph with order n≥2k+2 and ρ(G)≥ρ(K_(k,n-k)),then G contains all T_(2k+3) unless G≌K_(k,n-k).Finally,we prove that among all outerplanar bipartite graphs on n≥308026 vertices,K_(1,n-1) attains the maximum spectral radius.展开更多
The concept of matching energy was proposed by Gutman and Wagner firstly in 2012. Let G be a simple graph of order n and λ1, λ2, . . . , λn be the zeros of its matching polynomial. The matching energy of a graph G ...The concept of matching energy was proposed by Gutman and Wagner firstly in 2012. Let G be a simple graph of order n and λ1, λ2, . . . , λn be the zeros of its matching polynomial. The matching energy of a graph G is defined as ME(G) = Pni=1 |λi|. By the famous Coulson’s formula, matching energies can also be calculated by an improper integral depending on a parameter. A k-claw attaching graph Gu(k) refers to the graph obtained by attaching k pendent edges to the graph G at the vertex u, where u is called the root of Gu(k). In this paper, we use some theories of mathematical analysis to obtain a new technique to compare the matching energies of two k-claw attaching graphs Gu(k) and Hv(k) with the same order, that is, limk→∞[ME(Gu(k)) − ME(Hv(k))] = ME(G − u) − ME(H − v). By the technique, we finally determine unicyclic graphs of order n with the 9th to 13th minimal matching energies for all n ≥ 58.展开更多
A graph G is called d-degenerate if every subgraph of G has a vertex of degree at most d.It was known that planar graphs are 5-degenerate and every planar graph without k-cycles for some prescribed k∈{3,5,6}is 3-dege...A graph G is called d-degenerate if every subgraph of G has a vertex of degree at most d.It was known that planar graphs are 5-degenerate and every planar graph without k-cycles for some prescribed k∈{3,5,6}is 3-degenerate.In this paper,we show that if G is a planar graph without kites and 9-or 10-cycles,then G is 3-degenerate,hence 4-choosable and list vertex 2-arborable.展开更多
Determining the crossing number of a given graph is NP-complete. The cycle of length m is denoted by Cm = v1v2…vmv1. G^((1))_(m) (m ≥ 5) is the graph obtained from Cm by adding two edges v1v3 and vlvl+2 (3 ≤ l ≤ m...Determining the crossing number of a given graph is NP-complete. The cycle of length m is denoted by Cm = v1v2…vmv1. G^((1))_(m) (m ≥ 5) is the graph obtained from Cm by adding two edges v1v3 and vlvl+2 (3 ≤ l ≤ m−2), G^((2))m (m ≥ 4) is the graph obtained from Cm by adding two edges v1v3 and v2v4. The famous Zarankiewicz’s conjecture on the crossing number of the complete bipartite graph Km,n states that cr(Km,n)=Z(m,n)=[m/2][m-1/2][n/2[n-1/2].Based on Zarankiewicz’s conjecture, a natural problem is to study the change in the crossingnumber of the graphs obtained from the complete bipartite graph by adding certain edge sets.If Zarankiewicz’s conjecture is true, this paper proves that cr(G^((1))_(m)+Kn)=Z(m,n)+2[n/2] and cr(G^((2))_(m)+Kn)=Z(m,n)+n.展开更多
DP-coloring as a generalization of list coloring was introduced recently by Dvo˘r´ak and Postle.In this paper,we show that planar graphs without 5-cycles adjacent to two triangles are DP-4-colorable,which improve...DP-coloring as a generalization of list coloring was introduced recently by Dvo˘r´ak and Postle.In this paper,we show that planar graphs without 5-cycles adjacent to two triangles are DP-4-colorable,which improves the results of[Discrete Math.,2018,341(7):1983–1986]and[Discrete Appl.Math.,2020,277:245–251].展开更多
For a graph G,a vertex is said to be pendant if its neighborhood contains exactly one vertex.In this paper,we determine the extremal graphs among all n-vertex graphs with the minimum spectral radius andβpendant verti...For a graph G,a vertex is said to be pendant if its neighborhood contains exactly one vertex.In this paper,we determine the extremal graphs among all n-vertex graphs with the minimum spectral radius andβpendant vertices,whereβe{1,2,3,4,n-3,n-2,n-1}.展开更多
For a simple graph G,let A(G)and D(G)be the adjacency matrix and the diagonal degree matrix of G,respectively.[Appl.Anal.Discrete Math.,2017,11(1):81-107]defined the matrix A_(α)(G)of G as A_(α)(G)=αD(G)(1-α)A(G)...For a simple graph G,let A(G)and D(G)be the adjacency matrix and the diagonal degree matrix of G,respectively.[Appl.Anal.Discrete Math.,2017,11(1):81-107]defined the matrix A_(α)(G)of G as A_(α)(G)=αD(G)(1-α)A(G),α∈[0,1].The Aa-spectral radius is the largest eigenvalue of A_(α)(G).Let G_(n,β) be the set graphs with order n and dissociation numberβ.In this paper,we identify the b with maximal A_(α)-spectral radius among all graphs in G_(n,β).展开更多
文摘The products of graphs discussed in this paper are the following four kinds: the Cartesian product of graphs, the tensor product of graphs, the lexicographic product of graphs and the strong direct product of graphs. It is proved that:① If the graphs G 1 and G 2 are the connected graphs, then the Cartesian product, the lexicographic product and the strong direct product in the products of graphs, are the path positive graphs. ② If the tensor product is a path positive graph if and only if the graph G 1 and G 2 are the connected graphs, and the graph G 1 or G 2 has an odd cycle and max{ λ 1μ 1,λ nμ m}≥2 in which λ 1 and λ n [ or μ 1 and μ m] are maximum and minimum characteristic values of graph G 1 [ or G 2 ], respectively.
基金Supported by the National Natural Science Foundation of China(Grant Nos.11961041,12261055)the Key Project of Natural Science Foundation of Gansu Province(Grant No.24JRRA222)the Foundation for Innovative Fundamental Research Group Project of Gansu Province(Grant No.25JRRA805).
文摘In this paper,we first give a sufficient condition for a graph being fractional ID-[a,b]-factor-critical covered in terms of its independence number and minimum degree,which partially answers the problem posed by Sizhong Zhou,Hongxia Liu and Yang Xu(2022).Then,an A_(α)-spectral condition is given to ensure that G is a fractional ID-[a,b]-factor-critical covered graph and an(a,b,k)-factor-critical graph,respectively.In fact,(a,b,k)-factor-critical graph is a graph which has an[a,b]-factor for k=0.Thus,these above results extend the results of Jia Wei and Shenggui Zhang(2023)and Ao Fan,Ruifang Liu and Guoyan Ao(2023)in some sense.
基金Supported by the National Natural Science Foundation of China(Grant Nos.11171114,11401576)Hotan Prefecture Science and Technology Bureau General Project(Grant No.20220212)。
文摘A set S of vertices of a graph G is called a decycling set if G-S is acyclic.The smallest size of a decycling set is called the decycling number of G and is denoted by ∇(G).In this paper,we investigate the decycling number of type-k Halin graphs,focusing on those that are formed from trees that have just two degrees k and 3.For any type-k Halin graph G of order n,we prove that(k-2)n+k^(2)-4k+5/(k-1)^(2)≤∇(G)≤n+k-3/k-1.The result not only supports the largest forest conjecture due to Albertson and Berman(1976),but also offers a tight lower bound for the decycling number of type-3 Halin graphs and several type-k Halin graphs.Moreover,a new formula to determine the cardinality of any decycling set S of a type-k Halin graph G is provided.
基金Supported by the National Natural Science Foundation of China (10671081)
文摘A graph has exactly two main eigenvalues if and only if it is a 2-walk linear graph.In this paper,we show some necessary conditions that a 2-walk（a,b）-linear graph must obey.Using these conditions and some basic theorems in graph theory,we characterize all 2-walk linear graphs with small cyclic graphs without pendants.The results are given in sort on unicyclic,bicyclic,tricyclic graphs.
文摘A nowhere-zero k-flow on a graph G=(V(G),E(G))is a pair(D,f),where D is an orientation on E(G)and f:E(G)→{±1,±2,,±(k-1)}is a function such that the total outflow equals to the total inflow at each vertex.This concept was introduced by Tutte as an extension of face colorings,and Tutte in 1954 conjectured that every bridgeless graph admits a nowhere-zero 5-flow,known as the 5-Flow Conjecture.This conjecture is verified for some graph classes and remains unresolved as of today.In this paper,we show that every bridgeless graph of Euler genus at most 20 admits a nowhere-zero 5-flow,which improves several known results.
基金supported by the Natural Science Foundation of China(Grant No.72571150)。
文摘Detecting overlapping communities in attributed networks remains a significant challenge due to the complexity of jointly modeling topological structure and node attributes,the unknown number of communities,and the need to capture nodes with multiple memberships.To address these issues,we propose a novel framework named density peaks clustering with neutrosophic C-means.First,we construct a consensus embedding by aligning structure-based and attribute-based representations using spectral decomposition and canonical correlation analysis.Then,an improved density peaks algorithm automatically estimates the number of communities and selects initial cluster centers based on a newly designed cluster strength metric.Finally,a neutrosophic C-means algorithm refines the community assignments,modeling uncertainty and overlap explicitly.Experimental results on synthetic and real-world networks demonstrate that the proposed method achieves superior performance in terms of detection accuracy,stability,and its ability to identify overlapping structures.
基金supported by the Deep Earth Probe and Mineral Resources Exploration-National Science and Technology Major Project of China(Grant number:2024ZD1001105)National Natural Science Foundation of China(Grant number:42488201).
文摘Geologic time is an essential dimension in geological research,acting as a pivotal attribute that integrates data across various subdisciplines.The Geologic Time Scale(GTS)provides a formal framework for interpreting and communicating geologic time within the field of geological studies,such as macro-geological evolution and regional geologic surveys.
基金Supported by the National Natural Science Foundation of China(Grant No.12071260)。
文摘A graph whose edges are labeled either as positive or negative is called a signed graph.Hameed et al.introduced signed distance and distance compatibility in 2021,initially to characterize balanced signed graphs which have nice spectral properties.This article mainly studies the conjecture proposed by Shijin et al.on the distance compatibility of the direct product of signed graphs,and provides necessary and sufficient conditions for the distance compatibility of the direct product of signed graphs.Some further questions regarding distance compatibility are also posed.
基金The National Science Foundation of China(12371349,12471331)。
文摘Let G be a graph andαÎ[0,1),Nikiforov merged the adjacency matrix and the signless Laplacian matrix to A_(α)(G)=αD(G)+(1-α)A(G),where D(G)A(G)are the degree diagonal matrix and the adjacency matrix of G,respectively.The spectral radius of A_(α)(G)is called byα-spectral radius of the graph G.In this paper,we study the perturbation of the complete multipartite graphsα-spectral radius when move a vertex from a part to other part of the complete multipartite graphs.Moreover,we give some conditions when theα-spectral Turán of graphs implies the Turán theorem of graphs.
基金Supported by the National Natural Science Foundation of China(Grant No.11326221)
文摘Recently, Furtula et al. proposed a valuable predictive index in the study of the heat of formation in octanes and heptanes, the augmented Zagreb index （AZI index） of a graph G, which is defined asAZI（G） = ∑uv∈E（G）（dudv/du＋du-2）3,where E（G） is the edge set of G, d~ and d~ are the degrees of the terminal vertices u and v of edge uv, respectively. In this paper, we obtain the first five largest （resp., the first two smallest） AZI indices of connected graphs with n vertices. Moreover, we determine the trees of order n with the first three smallest AZI indices, the unicyclic graphs of order n with the minimum, the second minimum AZI indices, and the bicyclic graphs of order n with the minimum AZI index, respectively.
基金National Natural Science Foundation of China (No. 11071078,No. 11075057 )Open Research Funding Program of LGISEM and Shanghai Leading Academic Discipline Project,China (No. B407)
文摘A graph G is said to be determined by its Laplacian spectrum if any graph having the same Laplacian spectrum as G is isomorphic to G.We consider θ-graphs,that is,graphs obtained by subdividing the edges of the multigraph consist of three parallel edges.In this paper,some special θ-graphs are determined by their Laplacian spectra.
基金supported in part by the NSFC(11801496,11926352)the Fok Ying-Tung Education Foundation(China)the Hubei Key Laboratory of Applied Mathematics(Hubei University).
文摘In this paper,we investigate spacelike graphs defined over a domain Ω⊂M^(n) in the Lorentz manifold M^(n)×ℝ with the metric−ds^(2)+σ,where M^(n) is a complete Riemannian n-manifold with the metricσ,Ωhas piecewise smooth boundary,and ℝ denotes the Euclidean 1-space.We prove an interesting stability result for translating spacelike graphs in M^(n)×ℝ under a conformal transformation.
基金The National Natural Science Foundation of China(No.10971025)
文摘Let j, k and m be three positive integers, a circular m-L（j, k）-labeling of a graph G is a mapping f： V（G）→{0, 1, …, m-1}such that f（u）-f（v）m≥j if u and v are adjacent, and f（u）-f（v）m≥k if u and v are at distance two,where a-bm=min{a-b,m-a-b}. The minimum m such that there exists a circular m-L（j, k）-labeling of G is called the circular L（j, k）-labeling number of G and is denoted by σj, k（G）. For any two positive integers j and k with j≤k,the circular L（j, k）-labeling numbers of trees, the Cartesian product and the direct product of two complete graphs are determined.
基金Supported by NSFC(No.12271162)Natural Science Foundation of Shanghai(No.22ZR1416300).
文摘A graph G is H-free,if it contains no H as a subgraph.A graph G is said to be H-minor free,if it does not contain H as a minor.In 2010,Nikiforov asked that what the maximum spectral radius of an H-free graph of order n is.In this paper,we consider some Brualdi-Solheid-Turan type problems on bipartite graphs.In 2015,Zhai,Lin and Gong in[Linear Algebra Appl.,2015,471:21-27]proved that if G is a bipartite graph with order n≥2k+2 and ρ(G)≥ρ(K_(k,n-k)),then G contains a C_(2k+2) unless G≌K_(k,n-k).First,we give a new and more simple proof for the above theorem.Second,we prove that if G is a bipartite graph with order n≥2k+2 and ρ(G)≥ρ(K_(k,n-k)),then G contains all T_(2k+3) unless G≌K_(k,n-k).Finally,we prove that among all outerplanar bipartite graphs on n≥308026 vertices,K_(1,n-1) attains the maximum spectral radius.
基金Supported by the National Natural Science Foundation of China(Nos.12271439,11871398)the National College Students Innovation and Entrepreneurship Training Program(No.201910699173)。
文摘The concept of matching energy was proposed by Gutman and Wagner firstly in 2012. Let G be a simple graph of order n and λ1, λ2, . . . , λn be the zeros of its matching polynomial. The matching energy of a graph G is defined as ME(G) = Pni=1 |λi|. By the famous Coulson’s formula, matching energies can also be calculated by an improper integral depending on a parameter. A k-claw attaching graph Gu(k) refers to the graph obtained by attaching k pendent edges to the graph G at the vertex u, where u is called the root of Gu(k). In this paper, we use some theories of mathematical analysis to obtain a new technique to compare the matching energies of two k-claw attaching graphs Gu(k) and Hv(k) with the same order, that is, limk→∞[ME(Gu(k)) − ME(Hv(k))] = ME(G − u) − ME(H − v). By the technique, we finally determine unicyclic graphs of order n with the 9th to 13th minimal matching energies for all n ≥ 58.
文摘A graph G is called d-degenerate if every subgraph of G has a vertex of degree at most d.It was known that planar graphs are 5-degenerate and every planar graph without k-cycles for some prescribed k∈{3,5,6}is 3-degenerate.In this paper,we show that if G is a planar graph without kites and 9-or 10-cycles,then G is 3-degenerate,hence 4-choosable and list vertex 2-arborable.
基金Supported by Changsha Natural Science Foundation(No.kq2208001)the Key Project Funded by Hunan Provincial Department of Education(No.21A0590)。
文摘Determining the crossing number of a given graph is NP-complete. The cycle of length m is denoted by Cm = v1v2…vmv1. G^((1))_(m) (m ≥ 5) is the graph obtained from Cm by adding two edges v1v3 and vlvl+2 (3 ≤ l ≤ m−2), G^((2))m (m ≥ 4) is the graph obtained from Cm by adding two edges v1v3 and v2v4. The famous Zarankiewicz’s conjecture on the crossing number of the complete bipartite graph Km,n states that cr(Km,n)=Z(m,n)=[m/2][m-1/2][n/2[n-1/2].Based on Zarankiewicz’s conjecture, a natural problem is to study the change in the crossingnumber of the graphs obtained from the complete bipartite graph by adding certain edge sets.If Zarankiewicz’s conjecture is true, this paper proves that cr(G^((1))_(m)+Kn)=Z(m,n)+2[n/2] and cr(G^((2))_(m)+Kn)=Z(m,n)+n.
基金Partially supported by NSFC(No.12301436)NSF of Guangxi Province(No.2025GXNSFAA069811)。
文摘DP-coloring as a generalization of list coloring was introduced recently by Dvo˘r´ak and Postle.In this paper,we show that planar graphs without 5-cycles adjacent to two triangles are DP-4-colorable,which improves the results of[Discrete Math.,2018,341(7):1983–1986]and[Discrete Appl.Math.,2020,277:245–251].
文摘For a graph G,a vertex is said to be pendant if its neighborhood contains exactly one vertex.In this paper,we determine the extremal graphs among all n-vertex graphs with the minimum spectral radius andβpendant vertices,whereβe{1,2,3,4,n-3,n-2,n-1}.
基金Supported by NSFC (Nos.12171089,12271235)NSF of Jiangsu (No.BK20190919)NSF of Fujian (No.2021J02048)。
文摘For a simple graph G,let A(G)and D(G)be the adjacency matrix and the diagonal degree matrix of G,respectively.[Appl.Anal.Discrete Math.,2017,11(1):81-107]defined the matrix A_(α)(G)of G as A_(α)(G)=αD(G)(1-α)A(G),α∈[0,1].The Aa-spectral radius is the largest eigenvalue of A_(α)(G).Let G_(n,β) be the set graphs with order n and dissociation numberβ.In this paper,we identify the b with maximal A_(α)-spectral radius among all graphs in G_(n,β).
