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 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.展开更多
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.展开更多
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,β).展开更多
Given two graphs G and H,the Ramsey number R(G,H)is the smallest positive integer N such that every 2-coloring of the edges of K_(N)contains either a red G or a blue H.Let K_(N-1)■K_(1,k)be the graph obtained from K_...Given two graphs G and H,the Ramsey number R(G,H)is the smallest positive integer N such that every 2-coloring of the edges of K_(N)contains either a red G or a blue H.Let K_(N-1)■K_(1,k)be the graph obtained from K_(N-1)by adding anew vertexνconnecting k vertices of K_(N-1).A graph G withχ(G)=k+1 is called edge-critical if G contains an edge e such thatχ(G-e)=k.A considerable amount of research has been conducted by previous scholars on Ramsey numbers ofgraphs.In this study,we show that for an edge-critical graph G with x(G)=k+1,when k≥2,1≥2,and n is sufficiently large,R(G,K_(1)+nK_(t))=knt+1 and r,(G,K_(1)+nK_(t))=(k-1)nt+1.展开更多
A dominating induced matching(DIM)of G is an induced matching that dominates every edge of G.In this note,we completely determine the number of DIMs in the generalized Petersen graph P(n,k).We prove that if P(n,k)is a...A dominating induced matching(DIM)of G is an induced matching that dominates every edge of G.In this note,we completely determine the number of DIMs in the generalized Petersen graph P(n,k).We prove that if P(n,k)is a generalized Petersen graph with n=0(mod 5)and k=2,3(mod 5),then E(P(n,k))can be partitioned into five DIMs.Meanwhile,in the left cases k=0,1,4(mod 5),we build some counterexamples to show that there exist some P(n,k)'s which are DIM-free.展开更多
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.展开更多
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.展开更多
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.展开更多
Graphs have been widely used in fields ranging from chemical informatics to social network analysis.Graph-related problems become increasingly significant,with subgraph matching standing out as one of the most challen...Graphs have been widely used in fields ranging from chemical informatics to social network analysis.Graph-related problems become increasingly significant,with subgraph matching standing out as one of the most challenging tasks.The goal of subgraph matching is to find all subgraphs in the data graph that are isomorphic to the query graph.Traditional methods mostly rely on search strategies with high computational complexity and are hard to apply to large-scale real datasets.With the advent of graph neural networks(GNNs),researchers have turned to GNNs to address subgraph matching problems.However,the multi-attributed features on nodes and edges are overlooked during the learning of graphs,which causes inaccurate results in real-world scenarios.To tackle this problem,we propose a novel model called subgraph matching on multi-attributed graph network(SGMAN).SGMAN first utilizes improved line graphs to capture node and edge features.Then,SGMAN integrates GNN and contrastive learning(CL)to derive graph representation embeddings and calculate the matching matrix to represent the matching results.We conduct experiments on public datasets,and the results affirm the superior performance of our model.展开更多
Let R be afinite commutative ring with identity 1.The U-clean graph of R,denoted by U-Cl(R),is a graph with vertices in form(e,u),where e is a nonzero idempotent of R and u is a unit of R.In this paper,some basic prope...Let R be afinite commutative ring with identity 1.The U-clean graph of R,denoted by U-Cl(R),is a graph with vertices in form(e,u),where e is a nonzero idempotent of R and u is a unit of R.In this paper,some basic properties of U-Cl(R)and the explicit structures of U-Cl(Zp×Zq)are given,where p,q are primes.We prove that U-Cl(Zp×Zq)is Eulerlian if and only if p=2,q=2.Moreover,the clique number,the chromatic number of the U-clean graph for some classes of rings are given in this paper.展开更多
A Gallai k-coloring is a k-edge-coloring of a complete graph in which there are no rainbow triangles.For given graphs G_(1),G_(2),G_(3)and nonnegative integers r,s,t with k=r+s+t,the k-colored Gallai-Ramsey number grk...A Gallai k-coloring is a k-edge-coloring of a complete graph in which there are no rainbow triangles.For given graphs G_(1),G_(2),G_(3)and nonnegative integers r,s,t with k=r+s+t,the k-colored Gallai-Ramsey number grk(K_(3):r·G_(1),s·G_(2),t·G_(3))is the minimum integer n such that every Gallai k-colored Kncontains a monochromatic copy of G_(1)colored by one of the first r colors or a monochromatic copy of G_(2)colored by one of the middle s colors or a monochromatic copy of G_(3)colored by one of the last t colors.In this paper,we determine the value of GallaiRamsey number in the case that G_(1)=B_(3)^(+),G_(2)=S_(3)^(+)and G_(3)=K_(3).Then the Gallai-Ramsey numbers grk(K_(3):B_(3)^(+)),grk(K_(3):S_(3)^(+))and grk(K_(3):K_(3))are obtained,respectively.Furthermore,the Gallai-Ramsey numbers grk(K_(3):r·B_(3)^(+),(k-r)·S_(3)^(+)),grk(K_(3):r·B_(3)^(+),(k-r)·K_(3))and grk(K_(3):s·S_(3)^(+),(k-s)·K_(3))are obtained,respectively.展开更多
Knowledge graphs (KGs) offer a structured, machine-readable format for organizing complex information. In heterogeneous catalysis, where data on catalytic materials, reaction conditions, mechanisms, and synthesis rout...Knowledge graphs (KGs) offer a structured, machine-readable format for organizing complex information. In heterogeneous catalysis, where data on catalytic materials, reaction conditions, mechanisms, and synthesis routes are dispersed across diverse sources, KGs provide a semantic framework that supports data integration under the FAIR (Findable, Accessible, Interoperable, and Reusable) principles. This review aims to survey recent developments in catalysis KGs, describe the main techniques for graph construction, and highlight how artificial intelligence, particularly large language models (LLMs), enhances graph generation and query. We conducted a systematic analysis of the literature, focusing on ontology-guided text mining pipelines, graph population methods, and maintenance strategies. Our review identifies key trends: ontology-based approaches enable the automated extraction of domain knowledge, LLM-driven retrieval-augmented generation supports natural-language queries, and scalable graph architectures range from a few thousand to over a million triples. We discuss state-of-the-art applications, such as catalyst recommendation systems and reaction mechanism discovery tools, and examine the major challenges, including data heterogeneity, ontology alignment, and long-term graph curation. We conclude that KGs, when combined with AI methods, hold significant promise for accelerating catalyst discovery and knowledge management, but progress depends on establishing community standards for ontology development and maintenance. This review provides a roadmap for researchers seeking to leverage KGs to advance heterogeneous catalysis research.展开更多
Knowledge graphs convey precise semantic information that can be effectively interpreted by neural networks,and generating descriptive text based on these graphs places significant emphasis on content consistency.Howe...Knowledge graphs convey precise semantic information that can be effectively interpreted by neural networks,and generating descriptive text based on these graphs places significant emphasis on content consistency.However,knowledge graphs are inadequate for providing additional linguistic features such as paragraph structure and expressive modes,making it challenging to ensure content coherence in generating text that spans multiple sentences.This lack of coherence can further compromise the overall consistency of the content within a paragraph.In this work,we present the generation of scientific abstracts by leveraging knowledge graphs,with a focus on enhancing both content consistency and coherence.In particular,we construct the ACL Abstract Graph Dataset(ACL-AGD)which pairs knowledge graphs with text,incorporating sentence labels to guide text structure and diverse expressions.We then implement a Siamese network to complement and concretize the entities and relations based on paragraph structure by accomplishing two tasks:graph-to-text generation and entity alignment.Extensive experiments demonstrate that the logical paragraphs generated by our method exhibit entities with a uniform position distribution and appropriate frequency.In terms of content,our method accurately represents the information encoded in the knowledge graph,prevents the generation of irrelevant content,and achieves coherent and non-redundant adjacent sentences,even with a shared knowledge graph.展开更多
基金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 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.
文摘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 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,β).
基金supported by the National Key Research and Development Program of China(2023YFA1010200,2020YFA0713100)the National Natural Science Foundation of China(12071453)the Innovation Program for Quantum Science and Technology(2021ZD0302902).
文摘Given two graphs G and H,the Ramsey number R(G,H)is the smallest positive integer N such that every 2-coloring of the edges of K_(N)contains either a red G or a blue H.Let K_(N-1)■K_(1,k)be the graph obtained from K_(N-1)by adding anew vertexνconnecting k vertices of K_(N-1).A graph G withχ(G)=k+1 is called edge-critical if G contains an edge e such thatχ(G-e)=k.A considerable amount of research has been conducted by previous scholars on Ramsey numbers ofgraphs.In this study,we show that for an edge-critical graph G with x(G)=k+1,when k≥2,1≥2,and n is sufficiently large,R(G,K_(1)+nK_(t))=knt+1 and r,(G,K_(1)+nK_(t))=(k-1)nt+1.
基金Ming Chen was supported by National Key Research and Development Program of China(No.2024YFA1013900)。
文摘A dominating induced matching(DIM)of G is an induced matching that dominates every edge of G.In this note,we completely determine the number of DIMs in the generalized Petersen graph P(n,k).We prove that if P(n,k)is a generalized Petersen graph with n=0(mod 5)and k=2,3(mod 5),then E(P(n,k))can be partitioned into five DIMs.Meanwhile,in the left cases k=0,1,4(mod 5),we build some counterexamples to show that there exist some P(n,k)'s which are DIM-free.
基金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 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 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.
文摘Graphs have been widely used in fields ranging from chemical informatics to social network analysis.Graph-related problems become increasingly significant,with subgraph matching standing out as one of the most challenging tasks.The goal of subgraph matching is to find all subgraphs in the data graph that are isomorphic to the query graph.Traditional methods mostly rely on search strategies with high computational complexity and are hard to apply to large-scale real datasets.With the advent of graph neural networks(GNNs),researchers have turned to GNNs to address subgraph matching problems.However,the multi-attributed features on nodes and edges are overlooked during the learning of graphs,which causes inaccurate results in real-world scenarios.To tackle this problem,we propose a novel model called subgraph matching on multi-attributed graph network(SGMAN).SGMAN first utilizes improved line graphs to capture node and edge features.Then,SGMAN integrates GNN and contrastive learning(CL)to derive graph representation embeddings and calculate the matching matrix to represent the matching results.We conduct experiments on public datasets,and the results affirm the superior performance of our model.
基金Supported by Anhui Provincial Natural Science Foundation(2008085MA06)the Key Project of Anhui Education Committee(gxyqZD2019009)。
文摘Let R be afinite commutative ring with identity 1.The U-clean graph of R,denoted by U-Cl(R),is a graph with vertices in form(e,u),where e is a nonzero idempotent of R and u is a unit of R.In this paper,some basic properties of U-Cl(R)and the explicit structures of U-Cl(Zp×Zq)are given,where p,q are primes.We prove that U-Cl(Zp×Zq)is Eulerlian if and only if p=2,q=2.Moreover,the clique number,the chromatic number of the U-clean graph for some classes of rings are given in this paper.
基金Supported by the National Natural Science Foundation of China(12161073)。
文摘A Gallai k-coloring is a k-edge-coloring of a complete graph in which there are no rainbow triangles.For given graphs G_(1),G_(2),G_(3)and nonnegative integers r,s,t with k=r+s+t,the k-colored Gallai-Ramsey number grk(K_(3):r·G_(1),s·G_(2),t·G_(3))is the minimum integer n such that every Gallai k-colored Kncontains a monochromatic copy of G_(1)colored by one of the first r colors or a monochromatic copy of G_(2)colored by one of the middle s colors or a monochromatic copy of G_(3)colored by one of the last t colors.In this paper,we determine the value of GallaiRamsey number in the case that G_(1)=B_(3)^(+),G_(2)=S_(3)^(+)and G_(3)=K_(3).Then the Gallai-Ramsey numbers grk(K_(3):B_(3)^(+)),grk(K_(3):S_(3)^(+))and grk(K_(3):K_(3))are obtained,respectively.Furthermore,the Gallai-Ramsey numbers grk(K_(3):r·B_(3)^(+),(k-r)·S_(3)^(+)),grk(K_(3):r·B_(3)^(+),(k-r)·K_(3))and grk(K_(3):s·S_(3)^(+),(k-s)·K_(3))are obtained,respectively.
基金support from the Full Bridge Fellowship for enabling the research stay at Virginia Tech.H.Xin acknowledge the financial support from the US Department of Energy,Office of Basic Energy Sciences under contract no.DE-SC0023323from the National Science Foundation through the grant 2245402 from CBET Catalysis and CDS&E programs.
文摘Knowledge graphs (KGs) offer a structured, machine-readable format for organizing complex information. In heterogeneous catalysis, where data on catalytic materials, reaction conditions, mechanisms, and synthesis routes are dispersed across diverse sources, KGs provide a semantic framework that supports data integration under the FAIR (Findable, Accessible, Interoperable, and Reusable) principles. This review aims to survey recent developments in catalysis KGs, describe the main techniques for graph construction, and highlight how artificial intelligence, particularly large language models (LLMs), enhances graph generation and query. We conducted a systematic analysis of the literature, focusing on ontology-guided text mining pipelines, graph population methods, and maintenance strategies. Our review identifies key trends: ontology-based approaches enable the automated extraction of domain knowledge, LLM-driven retrieval-augmented generation supports natural-language queries, and scalable graph architectures range from a few thousand to over a million triples. We discuss state-of-the-art applications, such as catalyst recommendation systems and reaction mechanism discovery tools, and examine the major challenges, including data heterogeneity, ontology alignment, and long-term graph curation. We conclude that KGs, when combined with AI methods, hold significant promise for accelerating catalyst discovery and knowledge management, but progress depends on establishing community standards for ontology development and maintenance. This review provides a roadmap for researchers seeking to leverage KGs to advance heterogeneous catalysis research.
文摘Knowledge graphs convey precise semantic information that can be effectively interpreted by neural networks,and generating descriptive text based on these graphs places significant emphasis on content consistency.However,knowledge graphs are inadequate for providing additional linguistic features such as paragraph structure and expressive modes,making it challenging to ensure content coherence in generating text that spans multiple sentences.This lack of coherence can further compromise the overall consistency of the content within a paragraph.In this work,we present the generation of scientific abstracts by leveraging knowledge graphs,with a focus on enhancing both content consistency and coherence.In particular,we construct the ACL Abstract Graph Dataset(ACL-AGD)which pairs knowledge graphs with text,incorporating sentence labels to guide text structure and diverse expressions.We then implement a Siamese network to complement and concretize the entities and relations based on paragraph structure by accomplishing two tasks:graph-to-text generation and entity alignment.Extensive experiments demonstrate that the logical paragraphs generated by our method exhibit entities with a uniform position distribution and appropriate frequency.In terms of content,our method accurately represents the information encoded in the knowledge graph,prevents the generation of irrelevant content,and achieves coherent and non-redundant adjacent sentences,even with a shared knowledge graph.
