In this paper,a new concept of an optimal complete multipartite decomposition of type 1 (type 2) of a complete n-partite graph Q n is proposed and another new concept of a normal complete multipartite decomposition o...In this paper,a new concept of an optimal complete multipartite decomposition of type 1 (type 2) of a complete n-partite graph Q n is proposed and another new concept of a normal complete multipartite decomposition of K n is introduced.It is showed that an optimal complete multipartite decomposition of type 1 of K n is a normal complete multipartite decomposition.As for any complete multipartite decomposition of K n,there is a derived complete multipartite decomposition for Q n.It is also showed that any optimal complete multipartite decomposition of type 1 of Q n is a derived decomposition of an optimal complete multipartite decomposition of type 1 of K n.Besides,some structural properties of an optimal complete multipartite decomposition of type 1 of K n are given.展开更多
Characterizing regular covers of symmetric graphs is one of the fundamental topics in the field of algebraic graph theory, and is often a key step for approaching general symmetric graphs. Complete graphs, which are t...Characterizing regular covers of symmetric graphs is one of the fundamental topics in the field of algebraic graph theory, and is often a key step for approaching general symmetric graphs. Complete graphs, which are typical symmetric graphs, naturally appear in the study of many symmetric graphs as normal quotient graphs. In this paper, a characterization of edge-transitive cyclic covers of complete graphs with prime power order is given by using the techniques of finite group theory and the related properties of coset graphs. Certain previous results are generalized and some new families of examples are founded.展开更多
In this study,using the method of contradiction and the pre-assignment of chromatic sets,we discuss the E-total coloring of complete bipartite graphs K_(5,n)(5≤n≤7 113) which are vertex-distinguished by multiple set...In this study,using the method of contradiction and the pre-assignment of chromatic sets,we discuss the E-total coloring of complete bipartite graphs K_(5,n)(5≤n≤7 113) which are vertex-distinguished by multiple sets.The vertex-distinguishing E-total chromatic numbers of this kind of graph are determined.展开更多
For a simple graph G,let matrix Q(G)=D(G) + A(G) be it's signless Laplacian matrix and Q G (λ)=det(λI Q) it's signless Laplacian characteristic polynomial,where D(G) denotes the diagonal matrix of vertex deg...For a simple graph G,let matrix Q(G)=D(G) + A(G) be it's signless Laplacian matrix and Q G (λ)=det(λI Q) it's signless Laplacian characteristic polynomial,where D(G) denotes the diagonal matrix of vertex degrees of G,A(G) denotes its adjacency matrix of G.If all eigenvalues of Q G (λ) are integral,then the graph G is called Q-integral.In this paper,we obtain that the signless Laplacian characteristic polynomials of the complete multi-partite graphs G=K(n_1,n_2,···,n_t).We prove that the complete t-partite graphs K(n,n,···,n)t are Q-integral and give a necessary and sufficient condition for the complete multipartite graphs K(m,···,m)s(n,···,n)t to be Q-integral.We also obtain that the signless Laplacian characteristic polynomials of the complete multipartite graphs K(m,···,m,)s1(n,···,n,)s2(l,···,l)s3.展开更多
Let G be a simple graph. An IE-total coloring f of G refers to a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color. Let C（u） be the set of colors of vertex u and edges i...Let G be a simple graph. An IE-total coloring f of G refers to a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color. Let C（u） be the set of colors of vertex u and edges incident to u under f. For an IE-total coloring f of G using k colors, if C（u） =fi C（v） for any two different vertices u and v of V（G）, then f is called a k-vertex-distinguishing IE-total-coloring of G, or a k-VDIET coloring of G for short. The ie iV., minimum number of colors required for a VDIET coloring of G is denoted by X,t[ 1, and it is called the VDIET chromatic number of G. We will give VDIET chromatic numbers for complete bipartite graph K4,n（n ≥ 4）, Kn,n （5 ≤ n ≤21） in this article.展开更多
A signed(res. signed total) Roman dominating function, SRDF(res.STRDF) for short, of a graph G =(V, E) is a function f : V → {-1, 1, 2} satisfying the conditions that(i)∑v∈N[v]f(v) ≥ 1(res.∑v∈N(v)f(v) ≥ 1) for ...A signed(res. signed total) Roman dominating function, SRDF(res.STRDF) for short, of a graph G =(V, E) is a function f : V → {-1, 1, 2} satisfying the conditions that(i)∑v∈N[v]f(v) ≥ 1(res.∑v∈N(v)f(v) ≥ 1) for any v ∈ V, where N [v] is the closed neighborhood and N(v) is the neighborhood of v, and(ii) every vertex v for which f(v) =-1 is adjacent to a vertex u for which f(u) = 2. The weight of a SRDF(res. STRDF) is the sum of its function values over all vertices.The signed(res. signed total) Roman domination number of G is the minimum weight among all signed(res. signed total) Roman dominating functions of G. In this paper,we compute the exact values of the signed(res. signed total) Roman domination numbers of complete bipartite graphs and wheels.展开更多
Let G be a simple graph. An IE-total coloring f of G is a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color. For each vertex x of G, let C(x) be the set of colors of verte...Let G be a simple graph. An IE-total coloring f of G is a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color. For each vertex x of G, let C(x) be the set of colors of vertex x and edges incident to x under f. For an IE-total coloring f of G using k colors, if C(u) ≠ C(v) for any two different vertices u and v of G, then f is called a k-vertex-distinguishing IE-total-coloring of G or a k-VDIET coloring of G for short. The minimum number of colors required for a VDIET coloring of G is denoted by χ_(vt)^(ie) (G) and is called vertex-distinguishing IE-total chromatic number or the VDIET chromatic number of G for short. The VDIET colorings of complete bipartite graphs K_(8,n)are discussed in this paper. Particularly, the VDIET chromatic number of K_(8,n) are obtained.展开更多
Let D(G) =(d_(ij))_(n×n) denote the distance matrix of a connected graph G with order n, where d_(ij) is equal to the distance between vertices viand vjin G. A graph is called distance integral if all eigenvalues...Let D(G) =(d_(ij))_(n×n) denote the distance matrix of a connected graph G with order n, where d_(ij) is equal to the distance between vertices viand vjin G. A graph is called distance integral if all eigenvalues of its distance matrix are integers. In 2014, Yang and Wang gave a sufficient and necessary condition for complete r-partite graphs K_(p1,p2,···,pr)=K_(a1·p1,a2·p2,···,as···ps) to be distance integral and obtained such distance integral graphs with s = 1, 2, 3, 4. However distance integral complete multipartite graphs K_(a1·p1,a2·p2,···,as·ps) with s > 4 have not been found. In this paper, we find and construct some infinite classes of these distance integral graphs K_(a1·p1,a2·p2,···,as·ps) with s = 5, 6. The problem of the existence of such distance integral graphs K_(a1·p1,a2·p2,···,as·ps) with arbitrarily large number s remains open.展开更多
We are concerned with the susceptible-infective-removed （SIR） model with random transition rates on complete graphs Cn with n vertices. We assign independent and identically distributed （i.i.d.） copies of a positi...We are concerned with the susceptible-infective-removed （SIR） model with random transition rates on complete graphs Cn with n vertices. We assign independent and identically distributed （i.i.d.） copies of a positive random variable ξ on each vertex as the recovery rates and i.i.d, copies of a positive random variable ρ on each edge as the edge infection weights. We assume that a susceptible vertex is infected by an infective one at rate proportional to the edge weight on the edge connecting these two vertices while an infective vertex becomes removed with rate equals the recovery rate on it, then we show that the model performs the following phase transition when at t = 0 one vertex is infective and others are susceptible. There exists λc 〉 0 such that when λ 〈 λc, the proportion r∞ of vertices which have ever been infective converges to 0 weakly as n → ＋∞ while when λ 〉 λc, there exist c（λ） 〉 0 and b（λ） 〉 0 such that for each n ≥ 1 with probability p ≥ b（λ）, the proportion r∞ ≥ c（λ）. Furthermore, we prove that Ac is the inverse of the production of the mean of p and the mean of the inverse of ξ.展开更多
The interval graph completion problem of a graph G includes two class problems： the profile problem and the pathwidth problem, denoted as P（G） and PW（G） respectively, where the profile problem is to find an inter...The interval graph completion problem of a graph G includes two class problems： the profile problem and the pathwidth problem, denoted as P（G） and PW（G） respectively, where the profile problem is to find an interval supergraph with the smallest possible number of edges; the pathwidth problem is to find an interval supergraph with the smallest possible cliquesize. These two class problems have important applications to numerical algebra, VLSI- layout and algorithm graph theory respectively; And they are known to be NP-complete for general graphs. Some classes of special graphs have been investigated in the literatures. In this paper the exact solutions of the profile and the pathwidth of the complete multipartite graph Kn1,n2,...nr （r≥ 2） are determined.展开更多
A function f:E(G)→{−1,1}is called a signed edge dominating function(SEDF for short)of G if f[e]=f(N[e])=Σ_( e′∈N[e])f(e′)≥1,for every edge e∈E(G).w(f)=Σ_(e∈E) f(e)is called the weight of f.The signed edge dom...A function f:E(G)→{−1,1}is called a signed edge dominating function(SEDF for short)of G if f[e]=f(N[e])=Σ_( e′∈N[e])f(e′)≥1,for every edge e∈E(G).w(f)=Σ_(e∈E) f(e)is called the weight of f.The signed edge domination numberγs′(G)of G is the minimum weight among all signed edge dominating functions of G.In this paper,we initiate the study of this parameter for G a complete multipartite graph.We provide the lower and upper bounds ofγs′(G)for G a complete r-partite graph with r even and all parts equal.展开更多
In the context of big data, many large-scale knowledge graphs have emerged to effectively organize the explosive growth of web data on the Internet. To select suitable knowledge graphs for use from many knowledge grap...In the context of big data, many large-scale knowledge graphs have emerged to effectively organize the explosive growth of web data on the Internet. To select suitable knowledge graphs for use from many knowledge graphs, quality assessment is particularly important. As an important thing of quality assessment, completeness assessment generally refers to the ratio of the current data volume to the total data volume.When evaluating the completeness of a knowledge graph, it is often necessary to refine the completeness dimension by setting different completeness metrics to produce more complete and understandable evaluation results for the knowledge graph.However, lack of awareness of requirements is the most problematic quality issue. In the actual evaluation process, the existing completeness metrics need to consider the actual application. Therefore, to accurately recommend suitable knowledge graphs to many users, it is particularly important to develop relevant measurement metrics and formulate measurement schemes for completeness. In this paper, we will first clarify the concept of completeness, establish each metric of completeness, and finally design a measurement proposal for the completeness of knowledge graphs.展开更多
A graph labeling is the assigning of labels to the vertices, edges, or both (usually non-negative integers), often satisfying some prescribed requirements. This terminology has become standard. A graph G's edges c...A graph labeling is the assigning of labels to the vertices, edges, or both (usually non-negative integers), often satisfying some prescribed requirements. This terminology has become standard. A graph G's edges can be colored by assigning a different color to each of its edges. The edge coloring is appropriate if adjacent edges are given different colors. In this work, we introduce a new labeling called NK-labeling. Let c:E(G)→ℕbe a proper edge coloring of G which induces a proper vertex coloring c′:V(G)→ℤndefined by c′(v)≡∑e∈Evc(e)modnSuch that Evis the set of edges incident with vin G. The minimum positive integer for which the graph G has NK-labeling called NK-chromatic index and denoted by χ′NK(G). We study the NK-labeling of several well-known classes of graphs. It is shown that the NK-chromatic of the path Pnfor n≥4is three and for odd n, the NK-chromatic of the complete graph Knis n. Other results dealing with the NK-labeling are also presented.展开更多
It is shown that r(W_m, K_n)≤(1+o(1))C_1n log n 2m-2m-2 for fixed even m≥4 and n→∞, and r(W_m, K_n)≤(1+o(1))C_2n 2mm+1 log n m+1m-1 for fixed odd m≥5 and n→∞, wher...It is shown that r(W_m, K_n)≤(1+o(1))C_1n log n 2m-2m-2 for fixed even m≥4 and n→∞, and r(W_m, K_n)≤(1+o(1))C_2n 2mm+1 log n m+1m-1 for fixed odd m≥5 and n→∞, where C_1=C_1(m)>0 and C_2=C_2(m)>0, in particular, C_2=12 if m=5 . It is obtained by the analytic method and using the function f_m(x)=∫ 1 _ 0 (1-t) 1m dtm+(x-m)t , x≥0 , m≥1 on the base of the asymptotic upper bounds for r(C_m, K_n) which were given by Caro, et al. Also, cn log n 52 ≤r(K_4, K_n)≤(1+o(1)) n 3 ( log n) 2 (as n→∞ ). Moreover, we give r(K_k+C_m, K_n)≤(1+o(1))C_5(m)n log n k+mm-2 for fixed even m≥4 and r(K_k+C_m, K_n)≤(1+o(1))C_6(m)n 2+(k+1)(m-1)2+k(m-1) log n k+2m-1 for fixed odd m≥3 (as n→∞ ).展开更多
With positive integers r,t and n,where n≥rt and t≥2,the maximum number of edges of a simple graph of order n is estimated,which does not contain r disjoint copies of K_r for r=2 and 3.
Most existing knowledge graph relationship prediction methods are unable to capture the complex information of multi-relational knowledge graphs,thus overlooking key details contained in different entity pairs and mak...Most existing knowledge graph relationship prediction methods are unable to capture the complex information of multi-relational knowledge graphs,thus overlooking key details contained in different entity pairs and making it difficult to aggregate more complex relational features.Moreover,the insufficient capture of multi-hop relational information limits the processing capability of the global structure of the graph and reduces the accuracy of the knowledge graph completion task.This paper uses graph neural networks to construct new message functions for different relations,which can be defined as the rotation from the source entity to the target entity in the complex vector space for each relation,thereby improving the relation perception.To further enrich the relational diversity of different entities,we capture themulti-hop structural information in complex graph structure relations by incorporating two-hop relations for each entity and adding auxiliary edges to various relation combinations in the knowledge graph,thereby aggregating more complex relations and improving the reasoning ability of complex relational information.To verify the effectiveness of the proposed method,we conducted experiments on the WN18RR and FB15k-237 standard datasets.The results show that the method proposed in this study outperforms most existing methods.展开更多
Multi-modal knowledge graph completion(MMKGC)aims to complete missing entities or relations in multi-modal knowledge graphs,thereby discovering more previously unknown triples.Due to the continuous growth of data and ...Multi-modal knowledge graph completion(MMKGC)aims to complete missing entities or relations in multi-modal knowledge graphs,thereby discovering more previously unknown triples.Due to the continuous growth of data and knowledge and the limitations of data sources,the visual knowledge within the knowledge graphs is generally of low quality,and some entities suffer from the issue of missing visual modality.Nevertheless,previous studies of MMKGC have primarily focused on how to facilitate modality interaction and fusion while neglecting the problems of low modality quality and modality missing.In this case,mainstream MMKGC models only use pre-trained visual encoders to extract features and transfer the semantic information to the joint embeddings through modal fusion,which inevitably suffers from problems such as error propagation and increased uncertainty.To address these problems,we propose a Multi-modal knowledge graph Completion model based on Super-resolution and Detailed Description Generation(MMCSD).Specifically,we leverage a pre-trained residual network to enhance the resolution and improve the quality of the visual modality.Moreover,we design multi-level visual semantic extraction and entity description generation,thereby further extracting entity semantics from structural triples and visual images.Meanwhile,we train a variational multi-modal auto-encoder and utilize a pre-trained multi-modal language model to complement the missing visual features.We conducted experiments on FB15K-237 and DB13K,and the results showed that MMCSD can effectively perform MMKGC and achieve state-of-the-art performance.展开更多
Let G be a simple graph. A total coloring f of G is called an E-total coloring if no two adjacent vertices of G receive the same color, and no edge of G receives the same color as one of its endpoints....Let G be a simple graph. A total coloring f of G is called an E-total coloring if no two adjacent vertices of G receive the same color, and no edge of G receives the same color as one of its endpoints. For an E-total coloring f of a graph G and any vertex x of G, let C（x） denote the set of colors of vertex x and of the edges incident with x, we call C（x） the color set of x. If C（u） ≠ C（v） for any two different vertices u and v of V （G）, then we say that f is a vertex-distinguishing E-total coloring of G or a VDET coloring of G for short. The minimum number of colors required for a VDET coloring of G is denoted by Хvt^e（G） and is called the VDE T chromatic number of G. The VDET coloring of complete bipartite graph K7,n （7 ≤ n ≤ 95） is discussed in this paper and the VDET chromatic number of K7,n （7 ≤ n ≤ 95） has been obtained.展开更多
For a graph G and two positive integers j and k, an m-L（j, k）-edge-labeling of G is an assignment on the edges to the set {0,..., m}, such that adjacent edges receive labels differing by at least j, and edges which ...For a graph G and two positive integers j and k, an m-L（j, k）-edge-labeling of G is an assignment on the edges to the set {0,..., m}, such that adjacent edges receive labels differing by at least j, and edges which are distance two apart receive labels differing by at least k. The λ′j,k-number of G is the minimum m of an m-L（j, k）-edge-labeling admitted by G.In this article, we study the L（1, 2）-edge-labeling for paths, cycles, complete graphs, complete multipartite graphs, infinite ？-regular trees and wheels.展开更多
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.展开更多
基金Supported by the National Natural Science Foundation of China( 1 0 2 71 1 1 0 )
文摘In this paper,a new concept of an optimal complete multipartite decomposition of type 1 (type 2) of a complete n-partite graph Q n is proposed and another new concept of a normal complete multipartite decomposition of K n is introduced.It is showed that an optimal complete multipartite decomposition of type 1 of K n is a normal complete multipartite decomposition.As for any complete multipartite decomposition of K n,there is a derived complete multipartite decomposition for Q n.It is also showed that any optimal complete multipartite decomposition of type 1 of Q n is a derived decomposition of an optimal complete multipartite decomposition of type 1 of K n.Besides,some structural properties of an optimal complete multipartite decomposition of type 1 of K n are given.
文摘Characterizing regular covers of symmetric graphs is one of the fundamental topics in the field of algebraic graph theory, and is often a key step for approaching general symmetric graphs. Complete graphs, which are typical symmetric graphs, naturally appear in the study of many symmetric graphs as normal quotient graphs. In this paper, a characterization of edge-transitive cyclic covers of complete graphs with prime power order is given by using the techniques of finite group theory and the related properties of coset graphs. Certain previous results are generalized and some new families of examples are founded.
基金Supported by the National Natural Science Foundation of China (11761064)。
文摘In this study,using the method of contradiction and the pre-assignment of chromatic sets,we discuss the E-total coloring of complete bipartite graphs K_(5,n)(5≤n≤7 113) which are vertex-distinguished by multiple sets.The vertex-distinguishing E-total chromatic numbers of this kind of graph are determined.
基金Supported by the NSFC(60863006)Supported by the NCET(-06-0912)Supported by the Science-Technology Foundation for Middle-aged and Yong Scientist of Qinghai University(2011-QGY-8)
文摘For a simple graph G,let matrix Q(G)=D(G) + A(G) be it's signless Laplacian matrix and Q G (λ)=det(λI Q) it's signless Laplacian characteristic polynomial,where D(G) denotes the diagonal matrix of vertex degrees of G,A(G) denotes its adjacency matrix of G.If all eigenvalues of Q G (λ) are integral,then the graph G is called Q-integral.In this paper,we obtain that the signless Laplacian characteristic polynomials of the complete multi-partite graphs G=K(n_1,n_2,···,n_t).We prove that the complete t-partite graphs K(n,n,···,n)t are Q-integral and give a necessary and sufficient condition for the complete multipartite graphs K(m,···,m)s(n,···,n)t to be Q-integral.We also obtain that the signless Laplacian characteristic polynomials of the complete multipartite graphs K(m,···,m,)s1(n,···,n,)s2(l,···,l)s3.
基金Supported by the National Natural Science Foundation of China (Grant Nos. 6116303761163054)+2 种基金the Scientific Research Project of Northwest Normal University (No. nwnu-kjcxgc-03-61)the Natural Foudation Project of Ningxia (No. NZ1154)the Scientific Research Foudation Project of Ningxia University (No. (E):ndzr10-7)
文摘Let G be a simple graph. An IE-total coloring f of G refers to a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color. Let C（u） be the set of colors of vertex u and edges incident to u under f. For an IE-total coloring f of G using k colors, if C（u） =fi C（v） for any two different vertices u and v of V（G）, then f is called a k-vertex-distinguishing IE-total-coloring of G, or a k-VDIET coloring of G for short. The ie iV., minimum number of colors required for a VDIET coloring of G is denoted by X,t[ 1, and it is called the VDIET chromatic number of G. We will give VDIET chromatic numbers for complete bipartite graph K4,n（n ≥ 4）, Kn,n （5 ≤ n ≤21） in this article.
基金The NSF(11271365)of Chinathe NSF(BK20151117)of Jiangsu Province
文摘A signed(res. signed total) Roman dominating function, SRDF(res.STRDF) for short, of a graph G =(V, E) is a function f : V → {-1, 1, 2} satisfying the conditions that(i)∑v∈N[v]f(v) ≥ 1(res.∑v∈N(v)f(v) ≥ 1) for any v ∈ V, where N [v] is the closed neighborhood and N(v) is the neighborhood of v, and(ii) every vertex v for which f(v) =-1 is adjacent to a vertex u for which f(u) = 2. The weight of a SRDF(res. STRDF) is the sum of its function values over all vertices.The signed(res. signed total) Roman domination number of G is the minimum weight among all signed(res. signed total) Roman dominating functions of G. In this paper,we compute the exact values of the signed(res. signed total) Roman domination numbers of complete bipartite graphs and wheels.
基金Supported by the National Natural Science Foundation of China（61163037, 61163054, 11261046, 61363060）
文摘Let G be a simple graph. An IE-total coloring f of G is a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color. For each vertex x of G, let C(x) be the set of colors of vertex x and edges incident to x under f. For an IE-total coloring f of G using k colors, if C(u) ≠ C(v) for any two different vertices u and v of G, then f is called a k-vertex-distinguishing IE-total-coloring of G or a k-VDIET coloring of G for short. The minimum number of colors required for a VDIET coloring of G is denoted by χ_(vt)^(ie) (G) and is called vertex-distinguishing IE-total chromatic number or the VDIET chromatic number of G for short. The VDIET colorings of complete bipartite graphs K_(8,n)are discussed in this paper. Particularly, the VDIET chromatic number of K_(8,n) are obtained.
基金Supported by the National Natural Science Foundation of China（11171273） Supported by the Graduate Starting Seed Fund of Northwestern Polytechnical University（Z2014173）
文摘Let D(G) =(d_(ij))_(n×n) denote the distance matrix of a connected graph G with order n, where d_(ij) is equal to the distance between vertices viand vjin G. A graph is called distance integral if all eigenvalues of its distance matrix are integers. In 2014, Yang and Wang gave a sufficient and necessary condition for complete r-partite graphs K_(p1,p2,···,pr)=K_(a1·p1,a2·p2,···,as···ps) to be distance integral and obtained such distance integral graphs with s = 1, 2, 3, 4. However distance integral complete multipartite graphs K_(a1·p1,a2·p2,···,as·ps) with s > 4 have not been found. In this paper, we find and construct some infinite classes of these distance integral graphs K_(a1·p1,a2·p2,···,as·ps) with s = 5, 6. The problem of the existence of such distance integral graphs K_(a1·p1,a2·p2,···,as·ps) with arbitrarily large number s remains open.
基金Acknowledgements The author is grateful to the reviewers. Their comments is a great help for him to improve this paper. In the original version, the author only proved that the main result holds under Assumption （7）. According to the reviewers＇ comments, he learned how to show that the main result holds under Assumption （1）. This work was supported by the National Natural Science Foundation of China （Grant No. 11501542） and the financial support from Beijing Jiaotong University （Grant No. KSRC16006536）.
文摘We are concerned with the susceptible-infective-removed （SIR） model with random transition rates on complete graphs Cn with n vertices. We assign independent and identically distributed （i.i.d.） copies of a positive random variable ξ on each vertex as the recovery rates and i.i.d, copies of a positive random variable ρ on each edge as the edge infection weights. We assume that a susceptible vertex is infected by an infective one at rate proportional to the edge weight on the edge connecting these two vertices while an infective vertex becomes removed with rate equals the recovery rate on it, then we show that the model performs the following phase transition when at t = 0 one vertex is infective and others are susceptible. There exists λc 〉 0 such that when λ 〈 λc, the proportion r∞ of vertices which have ever been infective converges to 0 weakly as n → ＋∞ while when λ 〉 λc, there exist c（λ） 〉 0 and b（λ） 〉 0 such that for each n ≥ 1 with probability p ≥ b（λ）, the proportion r∞ ≥ c（λ）. Furthermore, we prove that Ac is the inverse of the production of the mean of p and the mean of the inverse of ξ.
基金Supported by the Natural Science Foundation of Henan Province（082300460190） Sponsored by Program for Science and Technology Innovation Talents in Universities of Henan Province.
文摘The interval graph completion problem of a graph G includes two class problems： the profile problem and the pathwidth problem, denoted as P（G） and PW（G） respectively, where the profile problem is to find an interval supergraph with the smallest possible number of edges; the pathwidth problem is to find an interval supergraph with the smallest possible cliquesize. These two class problems have important applications to numerical algebra, VLSI- layout and algorithm graph theory respectively; And they are known to be NP-complete for general graphs. Some classes of special graphs have been investigated in the literatures. In this paper the exact solutions of the profile and the pathwidth of the complete multipartite graph Kn1,n2,...nr （r≥ 2） are determined.
基金Supported by the National Natural Science Foundation of China (Grant No. 71774078)。
文摘A function f:E(G)→{−1,1}is called a signed edge dominating function(SEDF for short)of G if f[e]=f(N[e])=Σ_( e′∈N[e])f(e′)≥1,for every edge e∈E(G).w(f)=Σ_(e∈E) f(e)is called the weight of f.The signed edge domination numberγs′(G)of G is the minimum weight among all signed edge dominating functions of G.In this paper,we initiate the study of this parameter for G a complete multipartite graph.We provide the lower and upper bounds ofγs′(G)for G a complete r-partite graph with r even and all parts equal.
基金supported by the National Key Laboratory for Comp lex Systems Simulation Foundation (6142006190301)。
文摘In the context of big data, many large-scale knowledge graphs have emerged to effectively organize the explosive growth of web data on the Internet. To select suitable knowledge graphs for use from many knowledge graphs, quality assessment is particularly important. As an important thing of quality assessment, completeness assessment generally refers to the ratio of the current data volume to the total data volume.When evaluating the completeness of a knowledge graph, it is often necessary to refine the completeness dimension by setting different completeness metrics to produce more complete and understandable evaluation results for the knowledge graph.However, lack of awareness of requirements is the most problematic quality issue. In the actual evaluation process, the existing completeness metrics need to consider the actual application. Therefore, to accurately recommend suitable knowledge graphs to many users, it is particularly important to develop relevant measurement metrics and formulate measurement schemes for completeness. In this paper, we will first clarify the concept of completeness, establish each metric of completeness, and finally design a measurement proposal for the completeness of knowledge graphs.
文摘A graph labeling is the assigning of labels to the vertices, edges, or both (usually non-negative integers), often satisfying some prescribed requirements. This terminology has become standard. A graph G's edges can be colored by assigning a different color to each of its edges. The edge coloring is appropriate if adjacent edges are given different colors. In this work, we introduce a new labeling called NK-labeling. Let c:E(G)→ℕbe a proper edge coloring of G which induces a proper vertex coloring c′:V(G)→ℤndefined by c′(v)≡∑e∈Evc(e)modnSuch that Evis the set of edges incident with vin G. The minimum positive integer for which the graph G has NK-labeling called NK-chromatic index and denoted by χ′NK(G). We study the NK-labeling of several well-known classes of graphs. It is shown that the NK-chromatic of the path Pnfor n≥4is three and for odd n, the NK-chromatic of the complete graph Knis n. Other results dealing with the NK-labeling are also presented.
文摘It is shown that r(W_m, K_n)≤(1+o(1))C_1n log n 2m-2m-2 for fixed even m≥4 and n→∞, and r(W_m, K_n)≤(1+o(1))C_2n 2mm+1 log n m+1m-1 for fixed odd m≥5 and n→∞, where C_1=C_1(m)>0 and C_2=C_2(m)>0, in particular, C_2=12 if m=5 . It is obtained by the analytic method and using the function f_m(x)=∫ 1 _ 0 (1-t) 1m dtm+(x-m)t , x≥0 , m≥1 on the base of the asymptotic upper bounds for r(C_m, K_n) which were given by Caro, et al. Also, cn log n 52 ≤r(K_4, K_n)≤(1+o(1)) n 3 ( log n) 2 (as n→∞ ). Moreover, we give r(K_k+C_m, K_n)≤(1+o(1))C_5(m)n log n k+mm-2 for fixed even m≥4 and r(K_k+C_m, K_n)≤(1+o(1))C_6(m)n 2+(k+1)(m-1)2+k(m-1) log n k+2m-1 for fixed odd m≥3 (as n→∞ ).
文摘With positive integers r,t and n,where n≥rt and t≥2,the maximum number of edges of a simple graph of order n is estimated,which does not contain r disjoint copies of K_r for r=2 and 3.
文摘Most existing knowledge graph relationship prediction methods are unable to capture the complex information of multi-relational knowledge graphs,thus overlooking key details contained in different entity pairs and making it difficult to aggregate more complex relational features.Moreover,the insufficient capture of multi-hop relational information limits the processing capability of the global structure of the graph and reduces the accuracy of the knowledge graph completion task.This paper uses graph neural networks to construct new message functions for different relations,which can be defined as the rotation from the source entity to the target entity in the complex vector space for each relation,thereby improving the relation perception.To further enrich the relational diversity of different entities,we capture themulti-hop structural information in complex graph structure relations by incorporating two-hop relations for each entity and adding auxiliary edges to various relation combinations in the knowledge graph,thereby aggregating more complex relations and improving the reasoning ability of complex relational information.To verify the effectiveness of the proposed method,we conducted experiments on the WN18RR and FB15k-237 standard datasets.The results show that the method proposed in this study outperforms most existing methods.
基金funded by Research Project,grant number BHQ090003000X03。
文摘Multi-modal knowledge graph completion(MMKGC)aims to complete missing entities or relations in multi-modal knowledge graphs,thereby discovering more previously unknown triples.Due to the continuous growth of data and knowledge and the limitations of data sources,the visual knowledge within the knowledge graphs is generally of low quality,and some entities suffer from the issue of missing visual modality.Nevertheless,previous studies of MMKGC have primarily focused on how to facilitate modality interaction and fusion while neglecting the problems of low modality quality and modality missing.In this case,mainstream MMKGC models only use pre-trained visual encoders to extract features and transfer the semantic information to the joint embeddings through modal fusion,which inevitably suffers from problems such as error propagation and increased uncertainty.To address these problems,we propose a Multi-modal knowledge graph Completion model based on Super-resolution and Detailed Description Generation(MMCSD).Specifically,we leverage a pre-trained residual network to enhance the resolution and improve the quality of the visual modality.Moreover,we design multi-level visual semantic extraction and entity description generation,thereby further extracting entity semantics from structural triples and visual images.Meanwhile,we train a variational multi-modal auto-encoder and utilize a pre-trained multi-modal language model to complement the missing visual features.We conducted experiments on FB15K-237 and DB13K,and the results showed that MMCSD can effectively perform MMKGC and achieve state-of-the-art performance.
文摘Let G be a simple graph. A total coloring f of G is called an E-total coloring if no two adjacent vertices of G receive the same color, and no edge of G receives the same color as one of its endpoints. For an E-total coloring f of a graph G and any vertex x of G, let C（x） denote the set of colors of vertex x and of the edges incident with x, we call C（x） the color set of x. If C（u） ≠ C（v） for any two different vertices u and v of V （G）, then we say that f is a vertex-distinguishing E-total coloring of G or a VDET coloring of G for short. The minimum number of colors required for a VDET coloring of G is denoted by Хvt^e（G） and is called the VDE T chromatic number of G. The VDET coloring of complete bipartite graph K7,n （7 ≤ n ≤ 95） is discussed in this paper and the VDET chromatic number of K7,n （7 ≤ n ≤ 95） has been obtained.
基金Supported by the National Natural Science Foundation of China(Grant Nos.1097102510901035)
文摘For a graph G and two positive integers j and k, an m-L（j, k）-edge-labeling of G is an assignment on the edges to the set {0,..., m}, such that adjacent edges receive labels differing by at least j, and edges which are distance two apart receive labels differing by at least k. The λ′j,k-number of G is the minimum m of an m-L（j, k）-edge-labeling admitted by G.In this article, we study the L（1, 2）-edge-labeling for paths, cycles, complete graphs, complete multipartite graphs, infinite ？-regular trees and wheels.
基金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.
