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→∞ ).展开更多
The quantum search on the graph is a very important topic.In this work,we develop a theoretic method on searching of single vertex on the graph[Phys.Rev.Lett.114110503(2015)],and systematically study the search of man...The quantum search on the graph is a very important topic.In this work,we develop a theoretic method on searching of single vertex on the graph[Phys.Rev.Lett.114110503(2015)],and systematically study the search of many vertices on one low-connectivity graph,the joined complete graph.Our results reveal that,with the optimal jumping rate obtained from the theoretical method,we can find such target vertices at the time O(√N),where N is the number of total vertices.Therefore,the search of many vertices on the joined complete graph possessing quantum advantage has been achieved.展开更多
<div style="text-align:justify;"> <span style="font-family:Verdana;">In the field of design theory, the most well-known design is a Steiner Triple System. In general, a G-design on H is...<div style="text-align:justify;"> <span style="font-family:Verdana;">In the field of design theory, the most well-known design is a Steiner Triple System. In general, a G-design on H is an edge-disjoint decomposition of H into isomorphic copies of G. In a Steiner Triple system, a complete graph is decomposed into triangles. In this paper we let H be a complete graph with a hole and G be a complete graph on four vertices minus one edge, also referred to as a <img alt="" src="Edit_e69ee166-4bbc-48f5-8ba1-b446e7d3738c.png" /> . A complete graph with a hole, <img alt="" src="Edit_558c249b-55e8-4f3b-a043-e36d001c4250.png" />, consists of a complete graph on d vertices, <img alt="" src="Edit_cb1772f7-837c-4aea-b4a6-cb38565f5a8b.png" />, and a set of independent vertices of size v, V, where each vertex in V is adjacent to each vertex in <img alt="" src="Edit_cb1772f7-837c-4aea-b4a6-cb38565f5a8b.png" />. When d is even, we give two constructions for the decomposition of a complete graph with a hole into copies of <img alt="" src="Edit_e69ee166-4bbc-48f5-8ba1-b446e7d3738c.png" /> : the Alpha-Delta Construction, and the Alpha-Beta-Delta Construction. By restricting d and v so that <img alt="" src="Edit_6bb9e3b4-1769-4b28-bf89-bc97c47c637e.png" /><span style="white-space:nowrap;"> , we are able to resolve both of these cases for a subset of <img alt="" src="Edit_558c249b-55e8-4f3b-a043-e36d001c4250.png" />using difference methods and 1-factors.展开更多
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 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.展开更多
In this paper, the problem of construction of exponentially many minimum genus crouchdings of complete graphs in surfaces are studied. There are three approaches to solve this problem. The first approach is to constru...In this paper, the problem of construction of exponentially many minimum genus crouchdings of complete graphs in surfaces are studied. There are three approaches to solve this problem. The first approach is to construct exponentially many graphs by the theory of graceful labeling of paths; the second approach is to find a current assignment of the current graph by the theory of current graph; the third approach is to find exponentially many embedding （or rotation） schemes of complete graph by finding exponentially many distinct maximum genus embeddings of the current graph. According to this three approaches, we can construct exponentially many minimum genus embeddings of complete graph K12s＋8 in orientable surfaces, which show that there are at least 10/5 × （200/9）^s distinct minimum genus embeddings for K12s＋8 in orientable surfaces. We have also proved that K12s＋8 has at least 10/3× （200/9）^s distinct minimum genus embeddings in non-orientable surfaces.展开更多
In this paper, we consider the problem of construction of exponentially many distinct genus embeddings of complete graphs. There are three approaches to solve the problem. The first approach is to construct exponentia...In this paper, we consider the problem of construction of exponentially many distinct genus embeddings of complete graphs. There are three approaches to solve the problem. The first approach is to construct exponentially many current graphs by the theory of graceful labellings of paths; the second approach is to find a current assignment of the current graph by the theory of current graph; the third approach is to find exponentially many embedding（or rotation） scheme of complete graph by finding exponentially many distinct maximum genus embeddings of the current graph. According to these three approaches, we can construct exponentially many distinct genus embeddings of complete graph K12s＋3, which show that there are at least1/2× （200/9）s distinct genus embeddings for K12s＋3.展开更多
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 ξ.展开更多
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 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.展开更多
The bondage number of γ f, b f(G) , is defined to be the minimum cardinality of a set of edges whose removal from G results in a graph G′ satisfying γ f(G′)> γ f(G) . The reinforcement number of γ f, ...The bondage number of γ f, b f(G) , is defined to be the minimum cardinality of a set of edges whose removal from G results in a graph G′ satisfying γ f(G′)> γ f(G) . The reinforcement number of γ f, r f(G) , is defined to be the minimum cardinality of a set of edges which when added to G results in a graph G′ satisfying γ f(G′)< γ f(G) . G.S.Domke and R.C.Laskar initiated the study of them and gave exact values of b f(G) and r f(G) for some classes of graphs. Exact values of b f(G) and r f(G) for complete multipartite graphs are given and some results are extended.展开更多
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.展开更多
Kobayashi discussed some kinds of standard embeddings into 3-manifolds of spatial graphs. He introduced the concept of book presentation, which is a standard embedding of spatial graphs with good properties, and prove...Kobayashi discussed some kinds of standard embeddings into 3-manifolds of spatial graphs. He introduced the concept of book presentation, which is a standard embedding of spatial graphs with good properties, and proved that the book presentation of minimum sheets of Kn is unique up to the sheet translation and the ambient isotopy. In this present paper we give the definition of skeleton presentation presentation of minimum floors of a complete isotopy. of spatial graphs, and prove that the skeleton bipartite graph Km, is unique up to ambient.展开更多
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.展开更多
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 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.展开更多
文摘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→∞ ).
基金the National Key R&D Program of China(Grant No.2017YFA0303800)the National Natural Science Foundation of China(Grant Nos.91850205 and 11974046)。
文摘The quantum search on the graph is a very important topic.In this work,we develop a theoretic method on searching of single vertex on the graph[Phys.Rev.Lett.114110503(2015)],and systematically study the search of many vertices on one low-connectivity graph,the joined complete graph.Our results reveal that,with the optimal jumping rate obtained from the theoretical method,we can find such target vertices at the time O(√N),where N is the number of total vertices.Therefore,the search of many vertices on the joined complete graph possessing quantum advantage has been achieved.
文摘<div style="text-align:justify;"> <span style="font-family:Verdana;">In the field of design theory, the most well-known design is a Steiner Triple System. In general, a G-design on H is an edge-disjoint decomposition of H into isomorphic copies of G. In a Steiner Triple system, a complete graph is decomposed into triangles. In this paper we let H be a complete graph with a hole and G be a complete graph on four vertices minus one edge, also referred to as a <img alt="" src="Edit_e69ee166-4bbc-48f5-8ba1-b446e7d3738c.png" /> . A complete graph with a hole, <img alt="" src="Edit_558c249b-55e8-4f3b-a043-e36d001c4250.png" />, consists of a complete graph on d vertices, <img alt="" src="Edit_cb1772f7-837c-4aea-b4a6-cb38565f5a8b.png" />, and a set of independent vertices of size v, V, where each vertex in V is adjacent to each vertex in <img alt="" src="Edit_cb1772f7-837c-4aea-b4a6-cb38565f5a8b.png" />. When d is even, we give two constructions for the decomposition of a complete graph with a hole into copies of <img alt="" src="Edit_e69ee166-4bbc-48f5-8ba1-b446e7d3738c.png" /> : the Alpha-Delta Construction, and the Alpha-Beta-Delta Construction. By restricting d and v so that <img alt="" src="Edit_6bb9e3b4-1769-4b28-bf89-bc97c47c637e.png" /><span style="white-space:nowrap;"> , we are able to resolve both of these cases for a subset of <img alt="" src="Edit_558c249b-55e8-4f3b-a043-e36d001c4250.png" />using difference methods and 1-factors.
文摘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( 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.
基金Supported by NSFC(Grant Nos.10771225,11171114)the Scientific Research Pro jects of State Ethnic Affairs Commission(Grant No.14ZYZ016)
文摘In this paper, the problem of construction of exponentially many minimum genus crouchdings of complete graphs in surfaces are studied. There are three approaches to solve this problem. The first approach is to construct exponentially many graphs by the theory of graceful labeling of paths; the second approach is to find a current assignment of the current graph by the theory of current graph; the third approach is to find exponentially many embedding （or rotation） schemes of complete graph by finding exponentially many distinct maximum genus embeddings of the current graph. According to this three approaches, we can construct exponentially many minimum genus embeddings of complete graph K12s＋8 in orientable surfaces, which show that there are at least 10/5 × （200/9）^s distinct minimum genus embeddings for K12s＋8 in orientable surfaces. We have also proved that K12s＋8 has at least 10/3× （200/9）^s distinct minimum genus embeddings in non-orientable surfaces.
基金Supported by the National Natural Science Foundation of China(No.10771225,11171114)
文摘In this paper, we consider the problem of construction of exponentially many distinct genus embeddings of complete graphs. There are three approaches to solve the problem. The first approach is to construct exponentially many current graphs by the theory of graceful labellings of paths; the second approach is to find a current assignment of the current graph by the theory of current graph; the third approach is to find exponentially many embedding（or rotation） scheme of complete graph by finding exponentially many distinct maximum genus embeddings of the current graph. According to these three approaches, we can construct exponentially many distinct genus embeddings of complete graph K12s＋3, which show that there are at least1/2× （200/9）s distinct genus embeddings for K12s＋3.
基金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 ξ.
文摘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 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.
文摘The bondage number of γ f, b f(G) , is defined to be the minimum cardinality of a set of edges whose removal from G results in a graph G′ satisfying γ f(G′)> γ f(G) . The reinforcement number of γ f, r f(G) , is defined to be the minimum cardinality of a set of edges which when added to G results in a graph G′ satisfying γ f(G′)< γ f(G) . G.S.Domke and R.C.Laskar initiated the study of them and gave exact values of b f(G) and r f(G) for some classes of graphs. Exact values of b f(G) and r f(G) for complete multipartite graphs are given and some results are extended.
基金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 National Natural Science Foundation of China(Grant No.11271063)
文摘Kobayashi discussed some kinds of standard embeddings into 3-manifolds of spatial graphs. He introduced the concept of book presentation, which is a standard embedding of spatial graphs with good properties, and proved that the book presentation of minimum sheets of Kn is unique up to the sheet translation and the ambient isotopy. In this present paper we give the definition of skeleton presentation presentation of minimum floors of a complete isotopy. of spatial graphs, and prove that the skeleton bipartite graph Km, is unique up to ambient.
基金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 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.
基金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.
