Let k be a positive integer and G a bipartite graph with bipartition (X,Y). A perfect 1-k matching is an edge subset M of G such that each vertex in Y is incident with exactly one edge in M and each vertex in X is inc...Let k be a positive integer and G a bipartite graph with bipartition (X,Y). A perfect 1-k matching is an edge subset M of G such that each vertex in Y is incident with exactly one edge in M and each vertex in X is incident with exactly k edges in M. A perfect 1-k matching is an optimal semi-matching related to the load-balancing problem, where a semi-matching is an edge subset M such that each vertex in Y is incident with exactly one edge in M, and a vertex in X can be incident with an arbitrary number of edges in M. In this paper, we give three sufficient and necessary conditions for the existence of perfect 1-k matchings and for the existence of 1-k matchings covering | X |−dvertices in X, respectively, and characterize k-elementary bipartite graph which is a graph such that the subgraph induced by all k-allowed edges is connected, where an edge is k-allowed if it is contained in a perfect 1-k matching.展开更多
Let j, k and m be three positive integers, a circular m-L（j, k）-labeling of a graph G is a mapping f： V（G）→{0, 1, …, m-1}such that f（u）-f（v）m≥j if u and v are adjacent, and f（u）-f（v）m≥k if u and v are...Let j, k and m be three positive integers, a circular m-L（j, k）-labeling of a graph G is a mapping f： V（G）→{0, 1, …, m-1}such that f（u）-f（v）m≥j if u and v are adjacent, and f（u）-f（v）m≥k if u and v are at distance two,where a-bm=min{a-b,m-a-b}. The minimum m such that there exists a circular m-L（j, k）-labeling of G is called the circular L（j, k）-labeling number of G and is denoted by σj, k（G）. For any two positive integers j and k with j≤k,the circular L（j, k）-labeling numbers of trees, the Cartesian product and the direct product of two complete graphs are determined.展开更多
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.展开更多
Abstract It was shown that a uniquely vertex k-colorable graph of order n has minimum size n（k - 1） - （^k2）, and a uniquely vertex 3-colorable extremal graph with the minimum degree 3 can be constructed. In this n...Abstract It was shown that a uniquely vertex k-colorable graph of order n has minimum size n（k - 1） - （^k2）, and a uniquely vertex 3-colorable extremal graph with the minimum degree 3 can be constructed. In this note, we construct-an infinite familyof uniquely vertex k-colorable graphs of the order n, the size n（k - 1） - （^k2） and the minimum degree k by using a recursion method.展开更多
A k-tree of a connected graph G is a spanning tree with maximum degree at most k. The rupture degree for a connected graph G is defined by , where and , respectively, denote the order of the largest component and numb...A k-tree of a connected graph G is a spanning tree with maximum degree at most k. The rupture degree for a connected graph G is defined by , where and , respectively, denote the order of the largest component and number of components in . In this paper, we show that for a connected graph G, if for any cut-set , then G has a k-tree.展开更多
Text Summarization models facilitate biomedical clinicians and researchers in acquiring informative data from enormous domain-specific literature within less time and effort.Evaluating and selecting the most informati...Text Summarization models facilitate biomedical clinicians and researchers in acquiring informative data from enormous domain-specific literature within less time and effort.Evaluating and selecting the most informative sentences from biomedical articles is always challenging.This study aims to develop a dual-mode biomedical text summarization model to achieve enhanced coverage and information.The research also includes checking the fitment of appropriate graph ranking techniques for improved performance of the summarization model.The input biomedical text is mapped as a graph where meaningful sentences are evaluated as the central node and the critical associations between them.The proposed framework utilizes the top k similarity technique in a combination of UMLS and a sampled probability-based clustering method which aids in unearthing relevant meanings of the biomedical domain-specific word vectors and finding the best possible associations between crucial sentences.The quality of the framework is assessed via different parameters like information retention,coverage,readability,cohesion,and ROUGE scores in clustering and non-clustering modes.The significant benefits of the suggested technique are capturing crucial biomedical information with increased coverage and reasonable memory consumption.The configurable settings of combined parameters reduce execution time,enhance memory utilization,and extract relevant information outperforming other biomedical baseline models.An improvement of 17%is achieved when the proposed model is checked against similar biomedical text summarizers.展开更多
Let G = (V,E) be a simple graph without isolated vertices. For positive integer k, a 3-valued function f : V → {-1,0,1} is said to be a minus total k-subdominating function (MTkSF) if sum from (u∈N(v)) to f(u)≥1 fo...Let G = (V,E) be a simple graph without isolated vertices. For positive integer k, a 3-valued function f : V → {-1,0,1} is said to be a minus total k-subdominating function (MTkSF) if sum from (u∈N(v)) to f(u)≥1 for at least k vertices v in G, where N(v) is the open neighborhood of v. The minus total k-subdomination number γkt(G) equals the minimum weight of an MTkSF on G. In this paper, the values on the minus total k-subdomination number of some special graphs are investigated. Several lower bounds on γkt of general graphs and trees are obtained.展开更多
In this paper, a necessary condition for a bipartite graph λK m,n to be K 1,k factorizable and a sufficient condition for kK m,n to have a K 1,k factorization whenever k is a prime numbe...In this paper, a necessary condition for a bipartite graph λK m,n to be K 1,k factorizable and a sufficient condition for kK m,n to have a K 1,k factorization whenever k is a prime number are given.展开更多
This paper is motivated by the concept of the signed k-domination problem and dedicated to the complexity of the problem on graphs. For any fixed nonnegative integer k, we show that the signed k-domination problem is ...This paper is motivated by the concept of the signed k-domination problem and dedicated to the complexity of the problem on graphs. For any fixed nonnegative integer k, we show that the signed k-domination problem is NP-complete for doubly chordal graphs. For strongly chordal graphs and distance-hereditary graphs, we show that the signed k-domination problem can be solved in polynomial time. We also show that the problem is linear-time solvable for trees, interval graphs, and chordal comparability graphs.展开更多
A k-cyclic graph is a connected graph of order n and size n + k-1. In this paper, we determine the maximal signless Laplacian spectral radius and the corresponding extremal graph among all C_4-free k-cyclic graphs of ...A k-cyclic graph is a connected graph of order n and size n + k-1. In this paper, we determine the maximal signless Laplacian spectral radius and the corresponding extremal graph among all C_4-free k-cyclic graphs of order n. Furthermore, we determine the first three unicycles and bicyclic, C_4-free graphs whose spectral radius of the signless Laplacian is maximal. Similar results are obtained for the(combinatorial)展开更多
The P_(k)-path graph P_(k)(G)corresponding to a graph G has for vertices the set of all paths of length k in G.Two vertices are joined by an edge if and only if the intersection of the corresponding paths forms a path...The P_(k)-path graph P_(k)(G)corresponding to a graph G has for vertices the set of all paths of length k in G.Two vertices are joined by an edge if and only if the intersection of the corresponding paths forms a path of length k-1 in G,and their union forms either a cycle or a path of length k+1.Let Ek={(v,p),p E V(P_(k)(G)),v is an end vertex of p in G},we define total P_(k)-graphs T_(k)(G)as Yk(G)=(V(G)UV(P_(k)(G)),E(G)U E(PI(G))U Ek).In this note,we introduce total P,-graphs Th(G)and study their edge connectivity,as the generaliza-tion of total graphs.展开更多
The diameter of a graph G is the maximal distance between pairs of vertices of G. When a network is modeled as a graph,diameter is a measurement for maximum transmission delay. The k-diameter dk(G) of a graph G, which...The diameter of a graph G is the maximal distance between pairs of vertices of G. When a network is modeled as a graph,diameter is a measurement for maximum transmission delay. The k-diameter dk(G) of a graph G, which deals with k internally disjoint paths between pairs of vertices of G, is a extension of the diameter of G. It has widely studied in graph theory and computer science. The circulant graph is a group-theoretic model of a class of symmetric interconnection network. Let Cn(i, n / 2) be a circulant graph of order n whose spanning elements are i and n / 2, where n≥4 and n is even. In this paper, the diameter, 2-diameter and 3-diameter of the Cn(i, n / 2) are all obtained if gcd(n,i)=1, where the symbol gcd(n,i) denotes the maximum common divisor of n and i.展开更多
Parameters k-distance and k-diameter are extension of the distance and the diameter in graph theory. In this paper, the k-distance dk （x,y） between the any vertices x and y is first obtained in a connected circulant...Parameters k-distance and k-diameter are extension of the distance and the diameter in graph theory. In this paper, the k-distance dk （x,y） between the any vertices x and y is first obtained in a connected circulant graph G with order n （n is even） and degree 3 by removing some vertices from the neighbour set of the x. Then, the k-diameters of the connected circulant graphs with order n and degree 3 are given by using the k-diameter dk （x,y）.展开更多
文摘Let k be a positive integer and G a bipartite graph with bipartition (X,Y). A perfect 1-k matching is an edge subset M of G such that each vertex in Y is incident with exactly one edge in M and each vertex in X is incident with exactly k edges in M. A perfect 1-k matching is an optimal semi-matching related to the load-balancing problem, where a semi-matching is an edge subset M such that each vertex in Y is incident with exactly one edge in M, and a vertex in X can be incident with an arbitrary number of edges in M. In this paper, we give three sufficient and necessary conditions for the existence of perfect 1-k matchings and for the existence of 1-k matchings covering | X |−dvertices in X, respectively, and characterize k-elementary bipartite graph which is a graph such that the subgraph induced by all k-allowed edges is connected, where an edge is k-allowed if it is contained in a perfect 1-k matching.
基金The National Natural Science Foundation of China(No.10971025)
文摘Let j, k and m be three positive integers, a circular m-L（j, k）-labeling of a graph G is a mapping f： V（G）→{0, 1, …, m-1}such that f（u）-f（v）m≥j if u and v are adjacent, and f（u）-f（v）m≥k if u and v are at distance two,where a-bm=min{a-b,m-a-b}. The minimum m such that there exists a circular m-L（j, k）-labeling of G is called the circular L（j, k）-labeling number of G and is denoted by σj, k（G）. For any two positive integers j and k with j≤k,the circular L（j, k）-labeling numbers of trees, the Cartesian product and the direct product of two complete graphs are determined.
基金supported by 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.
基金Project supported by the National Natural Science Foundation of China （Grant No.10101010）, and the Natural Science Development Foundation of Shanghai Municipal Commission of Education （Grant No.05AZ04）
文摘Abstract It was shown that a uniquely vertex k-colorable graph of order n has minimum size n（k - 1） - （^k2）, and a uniquely vertex 3-colorable extremal graph with the minimum degree 3 can be constructed. In this note, we construct-an infinite familyof uniquely vertex k-colorable graphs of the order n, the size n（k - 1） - （^k2） and the minimum degree k by using a recursion method.
文摘A k-tree of a connected graph G is a spanning tree with maximum degree at most k. The rupture degree for a connected graph G is defined by , where and , respectively, denote the order of the largest component and number of components in . In this paper, we show that for a connected graph G, if for any cut-set , then G has a k-tree.
文摘Text Summarization models facilitate biomedical clinicians and researchers in acquiring informative data from enormous domain-specific literature within less time and effort.Evaluating and selecting the most informative sentences from biomedical articles is always challenging.This study aims to develop a dual-mode biomedical text summarization model to achieve enhanced coverage and information.The research also includes checking the fitment of appropriate graph ranking techniques for improved performance of the summarization model.The input biomedical text is mapped as a graph where meaningful sentences are evaluated as the central node and the critical associations between them.The proposed framework utilizes the top k similarity technique in a combination of UMLS and a sampled probability-based clustering method which aids in unearthing relevant meanings of the biomedical domain-specific word vectors and finding the best possible associations between crucial sentences.The quality of the framework is assessed via different parameters like information retention,coverage,readability,cohesion,and ROUGE scores in clustering and non-clustering modes.The significant benefits of the suggested technique are capturing crucial biomedical information with increased coverage and reasonable memory consumption.The configurable settings of combined parameters reduce execution time,enhance memory utilization,and extract relevant information outperforming other biomedical baseline models.An improvement of 17%is achieved when the proposed model is checked against similar biomedical text summarizers.
基金supported by the National Natural Science Foundation of China (Grant No.10571117)the Development Foundation of Shanghai Municipal Education Commission (Grant No.05AZ04)
文摘Let G = (V,E) be a simple graph without isolated vertices. For positive integer k, a 3-valued function f : V → {-1,0,1} is said to be a minus total k-subdominating function (MTkSF) if sum from (u∈N(v)) to f(u)≥1 for at least k vertices v in G, where N(v) is the open neighborhood of v. The minus total k-subdomination number γkt(G) equals the minimum weight of an MTkSF on G. In this paper, the values on the minus total k-subdomination number of some special graphs are investigated. Several lower bounds on γkt of general graphs and trees are obtained.
文摘In this paper, a necessary condition for a bipartite graph λK m,n to be K 1,k factorizable and a sufficient condition for kK m,n to have a K 1,k factorization whenever k is a prime number are given.
文摘This paper is motivated by the concept of the signed k-domination problem and dedicated to the complexity of the problem on graphs. For any fixed nonnegative integer k, we show that the signed k-domination problem is NP-complete for doubly chordal graphs. For strongly chordal graphs and distance-hereditary graphs, we show that the signed k-domination problem can be solved in polynomial time. We also show that the problem is linear-time solvable for trees, interval graphs, and chordal comparability graphs.
基金Supported by the National Natural Science Foundation of China（11171273） Supported by the Seed Foundation of Innovation and Creation for Graduate Students in Northwestern Polytechnical Uni- versity（Z2016170）
文摘A k-cyclic graph is a connected graph of order n and size n + k-1. In this paper, we determine the maximal signless Laplacian spectral radius and the corresponding extremal graph among all C_4-free k-cyclic graphs of order n. Furthermore, we determine the first three unicycles and bicyclic, C_4-free graphs whose spectral radius of the signless Laplacian is maximal. Similar results are obtained for the(combinatorial)
基金supported by Natural Sciences Foundation of Guangxi Province(2012GXNSFBA053005)
文摘The P_(k)-path graph P_(k)(G)corresponding to a graph G has for vertices the set of all paths of length k in G.Two vertices are joined by an edge if and only if the intersection of the corresponding paths forms a path of length k-1 in G,and their union forms either a cycle or a path of length k+1.Let Ek={(v,p),p E V(P_(k)(G)),v is an end vertex of p in G},we define total P_(k)-graphs T_(k)(G)as Yk(G)=(V(G)UV(P_(k)(G)),E(G)U E(PI(G))U Ek).In this note,we introduce total P,-graphs Th(G)and study their edge connectivity,as the generaliza-tion of total graphs.
文摘The diameter of a graph G is the maximal distance between pairs of vertices of G. When a network is modeled as a graph,diameter is a measurement for maximum transmission delay. The k-diameter dk(G) of a graph G, which deals with k internally disjoint paths between pairs of vertices of G, is a extension of the diameter of G. It has widely studied in graph theory and computer science. The circulant graph is a group-theoretic model of a class of symmetric interconnection network. Let Cn(i, n / 2) be a circulant graph of order n whose spanning elements are i and n / 2, where n≥4 and n is even. In this paper, the diameter, 2-diameter and 3-diameter of the Cn(i, n / 2) are all obtained if gcd(n,i)=1, where the symbol gcd(n,i) denotes the maximum common divisor of n and i.
文摘Parameters k-distance and k-diameter are extension of the distance and the diameter in graph theory. In this paper, the k-distance dk （x,y） between the any vertices x and y is first obtained in a connected circulant graph G with order n （n is even） and degree 3 by removing some vertices from the neighbour set of the x. Then, the k-diameters of the connected circulant graphs with order n and degree 3 are given by using the k-diameter dk （x,y）.
