Let G be a k-connected graph, and T be a subset of V（G）. If G-T is not connected,then T is said to be a cut-set of G. A k-cut-set T of G is a cut-set of G with │T│=k. Let T bea k-cut-set of a k-connected graph G. ...Let G be a k-connected graph, and T be a subset of V（G）. If G-T is not connected,then T is said to be a cut-set of G. A k-cut-set T of G is a cut-set of G with │T│=k. Let T bea k-cut-set of a k-connected graph G. If G - T can be partitioned into subgraphs G1 and G2such that │G1│≥ 2, │G2│ 〉 2, then we call T a nontrivial k-cut-set of G. Suppose that G is a（k-1）-connected graph without nontrivial （k - 1）-cut-set. Then we call G a quasi k-connectedgraph. In this paper, we prove that for any integer k ≥ 5, if G is a k-connected graph withoutK4-, then every vertex of G is incident with an edge whose contraction yields a quasi k-connectedgraph, and so there are at least │V（G）│/2 edges of G such that the contraction of every member ofthem results in a quasi k-connected graph.展开更多
A graph G possesses Hamiltonian s-properties when G is Hamilton-connected if s=1,Hamiltonian if s=0,and traceable if s=-1.Let S_A(G)=λ_n(G)-λ_1(G)and S_L(G)=μ_n(G)-μ_2(G)be the spread and the Laplacian spread of G...A graph G possesses Hamiltonian s-properties when G is Hamilton-connected if s=1,Hamiltonian if s=0,and traceable if s=-1.Let S_A(G)=λ_n(G)-λ_1(G)and S_L(G)=μ_n(G)-μ_2(G)be the spread and the Laplacian spread of G,respectively,whereλ_n(G)andλ_1(G)are the largest and smallest eigenvalues of G,andμ_n(G)andμ_2(G)are the largest and second smallest Laplacian eigenvalues of G,respectively.In this paper,we shall present two sufficient conditions involving S_A(G)and S_L(G)for a k-connected graph to possess Hamiltonian s-properties,respectively.We also derive a sufficient condition on the Laplacian eigenratio μ2(G)/μ(G) for a k-connected graph to possess Hamiltonian s-properties.展开更多
An edge e of a k-connected graph G is said to be a removable edge if G e is still kconnected, where G e denotes the graph obtained from G by deleting e to get G - e, and for any end vertex of e with degree k - 1 in ...An edge e of a k-connected graph G is said to be a removable edge if G e is still kconnected, where G e denotes the graph obtained from G by deleting e to get G - e, and for any end vertex of e with degree k - 1 in G - e, say x, delete x, and then add edges between any pair of non-adjacent vertices in NG-e（x）. The existence of removable edges of k-connected graphs and some properties of 3-connected graphs and 4-connected graphs have been investigated. In the present paper, we investigate some properties of k-connected graphs and study the distribution of removable edges on a cycle in a k-connected graph （k ≥ 4）.展开更多
An edge e of a k-connected graph G is said to be a removable edge if G O e is still k-connected, where G O e denotes the graph obtained from G by the following way： deleting e to get G - e, and for any end vertex of ...An edge e of a k-connected graph G is said to be a removable edge if G O e is still k-connected, where G O e denotes the graph obtained from G by the following way： deleting e to get G - e, and for any end vertex of e with degree k - 1 in G - e, say x, deleting x, and then adding edges between any pair of non-adjacent vertices in NG-e （x）. The existence of removable edges of k-connected graphs and some properties of k-connected graphs have been investigated. In the present paper, we investigate the distribution of removable edges on a spanning tree of a k-connected graph （k ≥ 4）.展开更多
Although there are polynomial algorithms of finding a 2-partition or a 3-partition for a simple undirected 2-connected or 3-connected graph respectively, there is no general algorithm of finding a k-partition for a k-...Although there are polynomial algorithms of finding a 2-partition or a 3-partition for a simple undirected 2-connected or 3-connected graph respectively, there is no general algorithm of finding a k-partition for a k-connected graph G = (V, E), where k is the vertex connectivity of G. In this paper, an O(k2n2) general algorithm of finding a k-partition for a k-connected graph is proposed, where n = |V|.展开更多
The atom-bond sum-connectivity(ABS)index,put forward by[J.Math.Chem.,2022,60(10):20812093],exhibits a strong link with the acentric factor of octane isomers.The experimental physico-chemical properties of octane isome...The atom-bond sum-connectivity(ABS)index,put forward by[J.Math.Chem.,2022,60(10):20812093],exhibits a strong link with the acentric factor of octane isomers.The experimental physico-chemical properties of octane isomers,such as boiling point,of formation are found to be better measured by the ABS index than by the Randi,atom-bond connectivity(ABC),and sum-connectivity(SC)indices.One important source of information for researching the molecular structure is the bounds for its topological indices.The extrema of the ABS index of the line,total,and Mycielski graphs are calculated in this work.Moreover,the pertinent extremal graphs were illustrated.展开更多
Bollobas and Gyarfas conjectured that for n 〉 4（k - 1） every 2-edge-coloring of Kn contains a monochromatic k-connected subgraph with at least n - 2k ＋ 2 vertices. Liu, et al. proved that the conjecture holds when...Bollobas and Gyarfas conjectured that for n 〉 4（k - 1） every 2-edge-coloring of Kn contains a monochromatic k-connected subgraph with at least n - 2k ＋ 2 vertices. Liu, et al. proved that the conjecture holds when n 〉 13k - 15. In this note, we characterize all the 2-edge-colorings of Kn where each monochromatic k-connected subgraph has at most n - 2k ＋ 2 vertices for n ≥ 13k - 15.展开更多
A graph is Hamiltonian if it contains a cycle that visits each vertex of the graph exactly once.A chord of a cycle C is an edge that joins two non-consecutive vertices of C.A graph of order n is chorded pancyclic if i...A graph is Hamiltonian if it contains a cycle that visits each vertex of the graph exactly once.A chord of a cycle C is an edge that joins two non-consecutive vertices of C.A graph of order n is chorded pancyclic if it contains a chorded cycle of length k for every integer k with 4≤k≤n.In 2018,Ferro and Lesniak gave an edge number conditon for the Hamiltonicity(and the chorded pancyclicity)of balanced and unbalanced k-partite graphs.In this paper,we extend the main results of Ferro and Lesniak,and provide an edge condition for the Hamiltonicity(and the chorded pancyclicity)of balanced and unbalanced k-partite graphs with given minimum degree,respectively.展开更多
Let Un be the set of connected unicyclic graphs of order n and girth g.Let C(T_(1),T_(2),...,T_(g))Un be obtained from a cycle v_(1)v_(2)…v_(g)v_(1)(in the anticlockwise direction)by identifying vi with the root of a...Let Un be the set of connected unicyclic graphs of order n and girth g.Let C(T_(1),T_(2),...,T_(g))Un be obtained from a cycle v_(1)v_(2)…v_(g)v_(1)(in the anticlockwise direction)by identifying vi with the root of a rooted tree Ti of order ni for each i=1,2,...,g,where ni≥1 and∑^(g)_(i=1)n_(i)=n.Let S(n_(1),n_(2),...,n_(g))be obtained from C(T_(1),T_(2),..,T_(g))by replacing each Ti by a rooted star Sni with the center as its root.Let U(n_(1),n_(2),...,ng)be the set of unicyclic graphs which differ from the unicyclic graph S(n_(1),n_(2),...,n_(g))only up to a permutation of ni's.In this paper,the graph with the minimal least signless Laplacian eigenvalue(respectively,the graph with maximum signless Laplacian spread)in U(n_(1),n_(2),...,n_(g))is determined.展开更多
Dear Editor,D2This letter presents a node feature similarity preserving graph convolutional framework P G.Graph neural networks(GNNs)have garnered significant attention for their efficacy in learning graph representat...Dear Editor,D2This letter presents a node feature similarity preserving graph convolutional framework P G.Graph neural networks(GNNs)have garnered significant attention for their efficacy in learning graph representations across diverse real-world applications.展开更多
Dear Editor,This letter addresses the critical challenge of preserving privacy in graph learning without compromising on data utility.Differential privacy(DP)is emerging as an effective method for privacy-preserving g...Dear Editor,This letter addresses the critical challenge of preserving privacy in graph learning without compromising on data utility.Differential privacy(DP)is emerging as an effective method for privacy-preserving graph learning.However,its application often diminishes data utility,especially for nodes with fewer neighbors in graph neural networks(GNNs).展开更多
Knowledge graphs often suffer from sparsity and incompleteness.Knowledge graph reasoning is an effective way to address these issues.Unlike static knowledge graph reasoning,which is invariant over time,dynamic knowled...Knowledge graphs often suffer from sparsity and incompleteness.Knowledge graph reasoning is an effective way to address these issues.Unlike static knowledge graph reasoning,which is invariant over time,dynamic knowledge graph reasoning is more challenging due to its temporal nature.In essence,within each time step in a dynamic knowledge graph,there exists structural dependencies among entities and relations,whereas between adjacent time steps,there exists temporal continuity.Based on these structural and temporal characteristics,we propose a model named“DKGR-DR”to learn distributed representations of entities and relations by combining recurrent neural networks and graph neural networks to capture structural dependencies and temporal continuity in DKGs.In addition,we construct a static attribute graph to represent entities’inherent properties.DKGR-DR is capable of modeling both dynamic and static aspects of entities,enabling effective entity prediction and relation prediction.We conduct experiments on ICEWS05-15,ICEWS18,and ICEWS14 to demonstrate that DKGR-DR achieves competitive performance.展开更多
Skin diseases affect millions worldwide.Early detection is key to preventing disfigurement,lifelong disability,or death.Dermoscopic images acquired in primary-care settings show high intra-class visual similarity and ...Skin diseases affect millions worldwide.Early detection is key to preventing disfigurement,lifelong disability,or death.Dermoscopic images acquired in primary-care settings show high intra-class visual similarity and severe class imbalance,and occasional imaging artifacts can create ambiguity for state-of-the-art convolutional neural networks(CNNs).We frame skin lesion recognition as graph-based reasoning and,to ensure fair evaluation and avoid data leakage,adopt a strict lesion-level partitioning strategy.Each image is first over-segmented using SLIC(Simple Linear Iterative Clustering)to produce perceptually homogeneous superpixels.These superpixels form the nodes of a region-adjacency graph whose edges encode spatial continuity.Node attributes are 1280-dimensional embeddings extracted with a lightweight yet expressive EfficientNet-B0 backbone,providing strong representational power at modest computational cost.The resulting graphs are processed by a five-layer Graph Attention Network(GAT)that learns to weight inter-node relationships dynamically and aggregates multi-hop context before classifying lesions into seven classes with a log-softmax output.Extensive experiments on the DermaMNIST benchmark show the proposed pipeline achieves 88.35%accuracy and 98.04%AUC,outperforming contemporary CNNs,AutoML approaches,and alternative graph neural networks.An ablation study indicates EfficientNet-B0 produces superior node descriptors compared with ResNet-18 and DenseNet,and that roughly five GAT layers strike a good balance between being too shallow and over-deep while avoiding oversmoothing.The method requires no data augmentation or external metadata,making it a drop-in upgrade for clinical computer-aided diagnosis systems.展开更多
基金supported by National Natural Science Foundation of China(11071016)Union Foundation of The Science and Technology Department of Guizhou Province,Anshun GovernmentAnshun University(Qiankehe LH Zi[2014]7500)
文摘Let G be a k-connected graph, and T be a subset of V（G）. If G-T is not connected,then T is said to be a cut-set of G. A k-cut-set T of G is a cut-set of G with │T│=k. Let T bea k-cut-set of a k-connected graph G. If G - T can be partitioned into subgraphs G1 and G2such that │G1│≥ 2, │G2│ 〉 2, then we call T a nontrivial k-cut-set of G. Suppose that G is a（k-1）-connected graph without nontrivial （k - 1）-cut-set. Then we call G a quasi k-connectedgraph. In this paper, we prove that for any integer k ≥ 5, if G is a k-connected graph withoutK4-, then every vertex of G is incident with an edge whose contraction yields a quasi k-connectedgraph, and so there are at least │V（G）│/2 edges of G such that the contraction of every member ofthem results in a quasi k-connected graph.
基金Supported by NSFC(Nos.12171089,12271235)NSF of Fujian Province(No.2021J02048)。
文摘A graph G possesses Hamiltonian s-properties when G is Hamilton-connected if s=1,Hamiltonian if s=0,and traceable if s=-1.Let S_A(G)=λ_n(G)-λ_1(G)and S_L(G)=μ_n(G)-μ_2(G)be the spread and the Laplacian spread of G,respectively,whereλ_n(G)andλ_1(G)are the largest and smallest eigenvalues of G,andμ_n(G)andμ_2(G)are the largest and second smallest Laplacian eigenvalues of G,respectively.In this paper,we shall present two sufficient conditions involving S_A(G)and S_L(G)for a k-connected graph to possess Hamiltonian s-properties,respectively.We also derive a sufficient condition on the Laplacian eigenratio μ2(G)/μ(G) for a k-connected graph to possess Hamiltonian s-properties.
基金Supported by the Science-technology Foundation for Young Scientists of Fujian Province （Grant No. 2007F3070） and National Natural Science Foundation of China （Grant No. 10831001）
文摘An edge e of a k-connected graph G is said to be a removable edge if G e is still kconnected, where G e denotes the graph obtained from G by deleting e to get G - e, and for any end vertex of e with degree k - 1 in G - e, say x, delete x, and then add edges between any pair of non-adjacent vertices in NG-e（x）. The existence of removable edges of k-connected graphs and some properties of 3-connected graphs and 4-connected graphs have been investigated. In the present paper, we investigate some properties of k-connected graphs and study the distribution of removable edges on a cycle in a k-connected graph （k ≥ 4）.
基金Supported by the National Natural Science Foundation of China(No.11171134)the Fujian Province Science Foundation(No.2013J01014,2011J01015,2007F3070)
文摘An edge e of a k-connected graph G is said to be a removable edge if G O e is still k-connected, where G O e denotes the graph obtained from G by the following way： deleting e to get G - e, and for any end vertex of e with degree k - 1 in G - e, say x, deleting x, and then adding edges between any pair of non-adjacent vertices in NG-e （x）. The existence of removable edges of k-connected graphs and some properties of k-connected graphs have been investigated. In the present paper, we investigate the distribution of removable edges on a spanning tree of a k-connected graph （k ≥ 4）.
文摘Although there are polynomial algorithms of finding a 2-partition or a 3-partition for a simple undirected 2-connected or 3-connected graph respectively, there is no general algorithm of finding a k-partition for a k-connected graph G = (V, E), where k is the vertex connectivity of G. In this paper, an O(k2n2) general algorithm of finding a k-partition for a k-connected graph is proposed, where n = |V|.
基金Supported by Ningbo NSF(No.2021J234)Zhejiang Provincial Philosophy and Social Sciences Planning Project(No.24NDJC057YB)。
文摘The atom-bond sum-connectivity(ABS)index,put forward by[J.Math.Chem.,2022,60(10):20812093],exhibits a strong link with the acentric factor of octane isomers.The experimental physico-chemical properties of octane isomers,such as boiling point,of formation are found to be better measured by the ABS index than by the Randi,atom-bond connectivity(ABC),and sum-connectivity(SC)indices.One important source of information for researching the molecular structure is the bounds for its topological indices.The extrema of the ABS index of the line,total,and Mycielski graphs are calculated in this work.Moreover,the pertinent extremal graphs were illustrated.
基金Supported by the National Natural Science Foundation of China(10701065 and 11101378)Zhejiang Provincial Natural Science Foundation(LY14A010009)
文摘Bollobas and Gyarfas conjectured that for n 〉 4（k - 1） every 2-edge-coloring of Kn contains a monochromatic k-connected subgraph with at least n - 2k ＋ 2 vertices. Liu, et al. proved that the conjecture holds when n 〉 13k - 15. In this note, we characterize all the 2-edge-colorings of Kn where each monochromatic k-connected subgraph has at most n - 2k ＋ 2 vertices for n ≥ 13k - 15.
文摘A graph is Hamiltonian if it contains a cycle that visits each vertex of the graph exactly once.A chord of a cycle C is an edge that joins two non-consecutive vertices of C.A graph of order n is chorded pancyclic if it contains a chorded cycle of length k for every integer k with 4≤k≤n.In 2018,Ferro and Lesniak gave an edge number conditon for the Hamiltonicity(and the chorded pancyclicity)of balanced and unbalanced k-partite graphs.In this paper,we extend the main results of Ferro and Lesniak,and provide an edge condition for the Hamiltonicity(and the chorded pancyclicity)of balanced and unbalanced k-partite graphs with given minimum degree,respectively.
基金This research is supported by NSFC(Nos.12171154,12301438)the Chenguang Program of Shanghai Education Development Foundation and Shanghai Municipal Education Commission(No.23CGA37)。
文摘Let Un be the set of connected unicyclic graphs of order n and girth g.Let C(T_(1),T_(2),...,T_(g))Un be obtained from a cycle v_(1)v_(2)…v_(g)v_(1)(in the anticlockwise direction)by identifying vi with the root of a rooted tree Ti of order ni for each i=1,2,...,g,where ni≥1 and∑^(g)_(i=1)n_(i)=n.Let S(n_(1),n_(2),...,n_(g))be obtained from C(T_(1),T_(2),..,T_(g))by replacing each Ti by a rooted star Sni with the center as its root.Let U(n_(1),n_(2),...,ng)be the set of unicyclic graphs which differ from the unicyclic graph S(n_(1),n_(2),...,n_(g))only up to a permutation of ni's.In this paper,the graph with the minimal least signless Laplacian eigenvalue(respectively,the graph with maximum signless Laplacian spread)in U(n_(1),n_(2),...,n_(g))is determined.
基金supported by the National Natural Science Foundation of China(62402399)the New Chongqing Youth Innovation Talent Project(CSTB2024NSCQ-QCXMX0035)。
文摘Dear Editor,D2This letter presents a node feature similarity preserving graph convolutional framework P G.Graph neural networks(GNNs)have garnered significant attention for their efficacy in learning graph representations across diverse real-world applications.
基金supported by the National Key Research and Development Program of China(2023YFF0612900,2023YFF0612902)the Natural Science Foundation of Beijing,China(4254086)+3 种基金the National Natural Science Foundation of China(62472032)the Open Project Funding of Key Laboratory of Mobile Application Innovation and Governance Technology,Ministry of Industry and Information Technology(2023IFS080601-K)the Beijing Institute of Technology Research Fund Program for Young Scholarsthe Young Elite Scientists Sponsorship Program by CAST(2023QNRC001)。
文摘Dear Editor,This letter addresses the critical challenge of preserving privacy in graph learning without compromising on data utility.Differential privacy(DP)is emerging as an effective method for privacy-preserving graph learning.However,its application often diminishes data utility,especially for nodes with fewer neighbors in graph neural networks(GNNs).
基金supported byNationalNatural Science Foundation of China(GrantNos.62071098,U24B20128)Sichuan Science and Technology Program(Grant No.2022YFG0319).
文摘Knowledge graphs often suffer from sparsity and incompleteness.Knowledge graph reasoning is an effective way to address these issues.Unlike static knowledge graph reasoning,which is invariant over time,dynamic knowledge graph reasoning is more challenging due to its temporal nature.In essence,within each time step in a dynamic knowledge graph,there exists structural dependencies among entities and relations,whereas between adjacent time steps,there exists temporal continuity.Based on these structural and temporal characteristics,we propose a model named“DKGR-DR”to learn distributed representations of entities and relations by combining recurrent neural networks and graph neural networks to capture structural dependencies and temporal continuity in DKGs.In addition,we construct a static attribute graph to represent entities’inherent properties.DKGR-DR is capable of modeling both dynamic and static aspects of entities,enabling effective entity prediction and relation prediction.We conduct experiments on ICEWS05-15,ICEWS18,and ICEWS14 to demonstrate that DKGR-DR achieves competitive performance.
基金funded by the Deanship of Graduate Studies and Scientific Research at Jouf University under grant No.(DGSSR-2025-02-01296).
文摘Skin diseases affect millions worldwide.Early detection is key to preventing disfigurement,lifelong disability,or death.Dermoscopic images acquired in primary-care settings show high intra-class visual similarity and severe class imbalance,and occasional imaging artifacts can create ambiguity for state-of-the-art convolutional neural networks(CNNs).We frame skin lesion recognition as graph-based reasoning and,to ensure fair evaluation and avoid data leakage,adopt a strict lesion-level partitioning strategy.Each image is first over-segmented using SLIC(Simple Linear Iterative Clustering)to produce perceptually homogeneous superpixels.These superpixels form the nodes of a region-adjacency graph whose edges encode spatial continuity.Node attributes are 1280-dimensional embeddings extracted with a lightweight yet expressive EfficientNet-B0 backbone,providing strong representational power at modest computational cost.The resulting graphs are processed by a five-layer Graph Attention Network(GAT)that learns to weight inter-node relationships dynamically and aggregates multi-hop context before classifying lesions into seven classes with a log-softmax output.Extensive experiments on the DermaMNIST benchmark show the proposed pipeline achieves 88.35%accuracy and 98.04%AUC,outperforming contemporary CNNs,AutoML approaches,and alternative graph neural networks.An ablation study indicates EfficientNet-B0 produces superior node descriptors compared with ResNet-18 and DenseNet,and that roughly five GAT layers strike a good balance between being too shallow and over-deep while avoiding oversmoothing.The method requires no data augmentation or external metadata,making it a drop-in upgrade for clinical computer-aided diagnosis systems.
