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}.展开更多
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.展开更多
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,β).展开更多
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 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 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.展开更多
Urban combat environments pose complex and variable challenges for UAV path planning due to multidimensional factors,such as static and dynamic obstructions as well as risks of exposure to enemy detection,which threat...Urban combat environments pose complex and variable challenges for UAV path planning due to multidimensional factors,such as static and dynamic obstructions as well as risks of exposure to enemy detection,which threaten flight safety and mission success.Traditional path planning methods typically depend solely on the distribution of static obstacles to generate collision-free paths,without accounting for constraints imposed by enemy detection and strike capabilities.Such a simplified approach can yield safety-compromising routes in highly complex urban airspace.To address these limitations,this study proposes a multi-parameter path planning method based on reachable airspace visibility graphs,which integrates UAV performance constraints,environmental limitations,and exposure risks.An innovative heuristic algorithm is developed to balance operational safety and efficiency by both exposure risks and path length.In the case study set in a typical mixed-use urban area,analysis of airspace visibility graphs reveals significant variations in exposure risk at different regions and altitudes due to building encroachments.Path optimization results indicate that the method can effectively generate covert and efficient flight paths by dynamically adjusting the exposure index,which represents the likelihood of enemy detection,and the path length,which corresponds to mission execution time.展开更多
In the context of digitalization,course resources exhibit multimodal characteristics,covering various forms such as text,images,and videos.Course knowledge and learning resources are becoming increasingly diverse,prov...In the context of digitalization,course resources exhibit multimodal characteristics,covering various forms such as text,images,and videos.Course knowledge and learning resources are becoming increasingly diverse,providing favorable conditions for students’in-depth and efficient learning.Against this backdrop,how to scientifically apply emerging technologies to automatically collect,process,and integrate digital learning resources such as voices,videos,and courseware texts,and better innovate the organization and presentation forms of course knowledge has become an important development direction for“artificial intelligence+education.”This article elaborates on the elements and characteristics of knowledge graphs,analyzes the construction steps of knowledge graphs,and explores the construction methods of multimodal course knowledge graphs from aspects such as dataset collection,course knowledge ontology identification,knowledge discovery,and association,providing references for the intelligent application of online open courses.展开更多
In 2012, Ponraj et al. defined a concept of k-product cordial labeling as follows: Let f be a map from V(G)to { 0,1,⋯,k−1 }where k is an integer, 1≤k≤| V(G) |. For each edge uvassign the label f(u)f(v)(modk). f is c...In 2012, Ponraj et al. defined a concept of k-product cordial labeling as follows: Let f be a map from V(G)to { 0,1,⋯,k−1 }where k is an integer, 1≤k≤| V(G) |. For each edge uvassign the label f(u)f(v)(modk). f is called a k-product cordial labeling if | vf(i)−vf(j) |≤1, and | ef(i)−ef(j) |≤1, i,j∈{ 0,1,⋯,k−1 }, where vf(x)and ef(x)denote the number of vertices and edges respectively labeled with x (x=0,1,⋯,k−1). Motivated by this concept, we further studied and established that several families of graphs admit k-product cordial labeling. In this paper, we show that the path graphs Pnadmit k-product cordial labeling.展开更多
Drug repurposing offers a promising alternative to traditional drug development and significantly re-duces costs and timelines by identifying new therapeutic uses for existing drugs.However,the current approaches ofte...Drug repurposing offers a promising alternative to traditional drug development and significantly re-duces costs and timelines by identifying new therapeutic uses for existing drugs.However,the current approaches often rely on limited data sources and simplistic hypotheses,which restrict their ability to capture the multi-faceted nature of biological systems.This study introduces adaptive multi-view learning(AMVL),a novel methodology that integrates chemical-induced transcriptional profiles(CTPs),knowledge graph(KG)embeddings,and large language model(LLM)representations,to enhance drug repurposing predictions.AMVL incorporates an innovative similarity matrix expansion strategy and leverages multi-view learning(MVL),matrix factorization,and ensemble optimization techniques to integrate heterogeneous multi-source data.Comprehensive evaluations on benchmark datasets(Fdata-set,Cdataset,and Ydataset)and the large-scale iDrug dataset demonstrate that AMVL outperforms state-of-the-art(SOTA)methods,achieving superior accuracy in predicting drug-disease associations across multiple metrics.Literature-based validation further confirmed the model's predictive capabilities,with seven out of the top ten predictions corroborated by post-2011 evidence.To promote transparency and reproducibility,all data and codes used in this study were open-sourced,providing resources for pro-cessing CTPs,KG,and LLM-based similarity calculations,along with the complete AMVL algorithm and benchmarking procedures.By unifying diverse data modalities,AMVL offers a robust and scalable so-lution for accelerating drug discovery,fostering advancements in translational medicine and integrating multi-omics data.We aim to inspire further innovations in multi-source data integration and support the development of more precise and efficient strategies for advancing drug discovery and translational medicine.展开更多
Data curation is vital for selecting effective demonstration examples in graph-to-text generation.However,evaluating the quality ofKnowledgeGraphs(KGs)remains challenging.Prior research exhibits a narrowfocus on struc...Data curation is vital for selecting effective demonstration examples in graph-to-text generation.However,evaluating the quality ofKnowledgeGraphs(KGs)remains challenging.Prior research exhibits a narrowfocus on structural statistics,such as the shortest path length,while the correctness of graphs in representing the associated text is rarely explored.To address this gap,we introduce a dual-perspective evaluation framework for KG-text data,based on the computation of structural adequacy and semantic alignment.Froma structural perspective,we propose the Weighted Incremental EdgeMethod(WIEM)to quantify graph completeness by leveraging agreement between relation models to predict possible edges between entities.WIEM targets to find increments from models on“unseen links”,whose presence is inversely proportional to the structural adequacy of the original KG in representing the text.From a semantic perspective,we evaluate how well a KG aligns with the text in capturing the intended meaning.To do so,we instruct a large language model to convert KGs into natural language andmeasure the similarity between generated and reference texts.Based on these computations,we apply a Top-K union method,integrating the structural and semantic modules,to rank and select high-quality KGs.We evaluate our framework against various approaches for selecting few-shot examples in graph-to-text generation.Experiments on theAssociation for Computational LinguisticsAbstract Graph Dataset(ACL-AGD)and Automatic Content Extraction 05(ACE05)dataset demonstrate the effectiveness of our approach in distinguishing KG-text data of different qualities,evidenced by the largest performance gap between top-and bottom-ranked examples.We also find that the top examples selected through our dual-perspective framework consistently yield better performance than those selected by traditional measures.These results highlight the importance of data curation in improving graph-to-text generation.展开更多
基金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 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.
基金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 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(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.
基金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.
基金supported by the Ministry of Industry and Information Technology(No.23100002022102001)。
文摘Urban combat environments pose complex and variable challenges for UAV path planning due to multidimensional factors,such as static and dynamic obstructions as well as risks of exposure to enemy detection,which threaten flight safety and mission success.Traditional path planning methods typically depend solely on the distribution of static obstacles to generate collision-free paths,without accounting for constraints imposed by enemy detection and strike capabilities.Such a simplified approach can yield safety-compromising routes in highly complex urban airspace.To address these limitations,this study proposes a multi-parameter path planning method based on reachable airspace visibility graphs,which integrates UAV performance constraints,environmental limitations,and exposure risks.An innovative heuristic algorithm is developed to balance operational safety and efficiency by both exposure risks and path length.In the case study set in a typical mixed-use urban area,analysis of airspace visibility graphs reveals significant variations in exposure risk at different regions and altitudes due to building encroachments.Path optimization results indicate that the method can effectively generate covert and efficient flight paths by dynamically adjusting the exposure index,which represents the likelihood of enemy detection,and the path length,which corresponds to mission execution time.
基金University-level Scientific Research Project in Natural Sciences“Research on the Retrieval Method of Multimodal First-Class Course Teaching Content Based on Knowledge Graph Collaboration”(GKY-2024KYYBK-31)。
文摘In the context of digitalization,course resources exhibit multimodal characteristics,covering various forms such as text,images,and videos.Course knowledge and learning resources are becoming increasingly diverse,providing favorable conditions for students’in-depth and efficient learning.Against this backdrop,how to scientifically apply emerging technologies to automatically collect,process,and integrate digital learning resources such as voices,videos,and courseware texts,and better innovate the organization and presentation forms of course knowledge has become an important development direction for“artificial intelligence+education.”This article elaborates on the elements and characteristics of knowledge graphs,analyzes the construction steps of knowledge graphs,and explores the construction methods of multimodal course knowledge graphs from aspects such as dataset collection,course knowledge ontology identification,knowledge discovery,and association,providing references for the intelligent application of online open courses.
文摘In 2012, Ponraj et al. defined a concept of k-product cordial labeling as follows: Let f be a map from V(G)to { 0,1,⋯,k−1 }where k is an integer, 1≤k≤| V(G) |. For each edge uvassign the label f(u)f(v)(modk). f is called a k-product cordial labeling if | vf(i)−vf(j) |≤1, and | ef(i)−ef(j) |≤1, i,j∈{ 0,1,⋯,k−1 }, where vf(x)and ef(x)denote the number of vertices and edges respectively labeled with x (x=0,1,⋯,k−1). Motivated by this concept, we further studied and established that several families of graphs admit k-product cordial labeling. In this paper, we show that the path graphs Pnadmit k-product cordial labeling.
基金supported by the National Natural Science Foundation of China(Grant No.:62101087)the China Postdoctoral Science Foundation(Grant No.:2021MD703942)+2 种基金the Chongqing Postdoctoral Research Project Special Funding,China(Grant No.:2021XM2016)the Science Foundation of Chongqing Municipal Commission of Education,China(Grant No.:KJQN202100642)the Chongqing Natural Science Foundation,China(Grant No.:cstc2021jcyj-msxmX0834).
文摘Drug repurposing offers a promising alternative to traditional drug development and significantly re-duces costs and timelines by identifying new therapeutic uses for existing drugs.However,the current approaches often rely on limited data sources and simplistic hypotheses,which restrict their ability to capture the multi-faceted nature of biological systems.This study introduces adaptive multi-view learning(AMVL),a novel methodology that integrates chemical-induced transcriptional profiles(CTPs),knowledge graph(KG)embeddings,and large language model(LLM)representations,to enhance drug repurposing predictions.AMVL incorporates an innovative similarity matrix expansion strategy and leverages multi-view learning(MVL),matrix factorization,and ensemble optimization techniques to integrate heterogeneous multi-source data.Comprehensive evaluations on benchmark datasets(Fdata-set,Cdataset,and Ydataset)and the large-scale iDrug dataset demonstrate that AMVL outperforms state-of-the-art(SOTA)methods,achieving superior accuracy in predicting drug-disease associations across multiple metrics.Literature-based validation further confirmed the model's predictive capabilities,with seven out of the top ten predictions corroborated by post-2011 evidence.To promote transparency and reproducibility,all data and codes used in this study were open-sourced,providing resources for pro-cessing CTPs,KG,and LLM-based similarity calculations,along with the complete AMVL algorithm and benchmarking procedures.By unifying diverse data modalities,AMVL offers a robust and scalable so-lution for accelerating drug discovery,fostering advancements in translational medicine and integrating multi-omics data.We aim to inspire further innovations in multi-source data integration and support the development of more precise and efficient strategies for advancing drug discovery and translational medicine.
文摘Data curation is vital for selecting effective demonstration examples in graph-to-text generation.However,evaluating the quality ofKnowledgeGraphs(KGs)remains challenging.Prior research exhibits a narrowfocus on structural statistics,such as the shortest path length,while the correctness of graphs in representing the associated text is rarely explored.To address this gap,we introduce a dual-perspective evaluation framework for KG-text data,based on the computation of structural adequacy and semantic alignment.Froma structural perspective,we propose the Weighted Incremental EdgeMethod(WIEM)to quantify graph completeness by leveraging agreement between relation models to predict possible edges between entities.WIEM targets to find increments from models on“unseen links”,whose presence is inversely proportional to the structural adequacy of the original KG in representing the text.From a semantic perspective,we evaluate how well a KG aligns with the text in capturing the intended meaning.To do so,we instruct a large language model to convert KGs into natural language andmeasure the similarity between generated and reference texts.Based on these computations,we apply a Top-K union method,integrating the structural and semantic modules,to rank and select high-quality KGs.We evaluate our framework against various approaches for selecting few-shot examples in graph-to-text generation.Experiments on theAssociation for Computational LinguisticsAbstract Graph Dataset(ACL-AGD)and Automatic Content Extraction 05(ACE05)dataset demonstrate the effectiveness of our approach in distinguishing KG-text data of different qualities,evidenced by the largest performance gap between top-and bottom-ranked examples.We also find that the top examples selected through our dual-perspective framework consistently yield better performance than those selected by traditional measures.These results highlight the importance of data curation in improving graph-to-text generation.
