E-Total Coloring of Complete Bipartite Graphs K_(5,n)(5≤n≤7 113)Which Are Vertex-Distinguished by Multiple Sets

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.

How to implement a knowledge graph completeness assessment with the guidance of user requirements

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.

Cycle Multiplicity of Total Graph of Complete Bipartite Graph

Cycle multiplicity of a graph G is the maximum number of edge disjoint cycles in G. In this paper, we determine the cycle multiplicity of and then obtain the formula of cycle multiplicity of total graph of complete bipartite graph, this generalizes the result for, which is given by M.M. Akbar Ali in [1].

A Temporal Knowledge Graph Embedding Model Based on Variable Translation

Knowledge representation learning(KRL)aims to encode entities and relationships in various knowledge graphs into low-dimensional continuous vectors.It is popularly used in knowledge graph completion(or link prediction)tasks.Translation-based knowledge representation learning methods perform well in knowledge graph completion(KGC).However,the translation principles adopted by these methods are too strict and cannot model complex entities and relationships(i.e.,N-1,1-N,and N-N)well.Besides,these traditional translation principles are primarily used in static knowledge graphs and overlook the temporal properties of triplet facts.Therefore,we propose a temporal knowledge graph embedding model based on variable translation(TKGE-VT).The model proposes a new variable translation principle,which enables flexible transformation between entities and relationship embedding.Meanwhile,this paper considers the temporal properties of both entities and relationships and applies the proposed principle of variable translation to temporal knowledge graphs.We conduct link prediction and triplet classification experiments on four benchmark datasets:WN11,WN18,FB13,and FB15K.Our model outperforms baseline models on multiple evaluation metrics according to the experimental results.

Inductive Relation Prediction by Disentangled Subgraph Structure

Currently,most existing inductive relation prediction approaches are based on subgraph structures,with subgraph features extracted using graph neural networks to predict relations.However,subgraphs may contain disconnected regions,which usually represent different semantic ranges.Because not all semantic information about the regions is helpful in relation prediction,we propose a relation prediction model based on a disentangled subgraph structure and implement a feature updating approach based on relevant semantic aggregation.To indirectly achieve the disentangled subgraph structure from a semantic perspective,the mapping of entity features into different semantic spaces and the aggregation of related semantics on each semantic space are updated.The disentangled model can focus on features having higher semantic relevance in the prediction,thus addressing a problem with existing approaches,which ignore the semantic differences in different subgraph structures.Furthermore,using a gated recurrent neural network,this model enhances the features of entities by sorting them by distance and extracting the path information in the subgraphs.Experimentally,it is shown that when there are numerous disconnected regions in the subgraph,our model outperforms existing mainstream models in terms of both Area Under the Curve-Precision-Recall(AUC-PR)and Hits@10.Experiments prove that semantic differences in the knowledge graph can be effectively distinguished and verify the effectiveness of this method.

Hyperbolic hierarchical graph attention network for knowledge graph completion

Utilizing graph neural networks for knowledge embedding to accomplish the task of knowledge graph completion(KGC)has become an important research area in knowledge graph completion.However,the number of nodes in the knowledge graph increases exponentially with the depth of the tree,whereas the distances of nodes in Euclidean space are second-order polynomial distances,whereby knowledge embedding using graph neural networks in Euclidean space will not represent the distances between nodes well.This paper introduces a novel approach called hyperbolic hierarchical graph attention network(H2GAT)to rectify this limitation.Firstly,the paper conducts knowledge representation in the hyperbolic space,effectively mitigating the issue of exponential growth of nodes with tree depth and consequent information loss.Secondly,it introduces a hierarchical graph atten-tion mechanism specifically designed for the hyperbolic space,allowing for enhanced capture of the network structure inherent in the knowledge graph.Finally,the efficacy of the proposed H2GAT model is evaluated on benchmark datasets,namely WN18RR and FB15K-237,thereby validating its effectiveness.The H2GAT model achieved 0.445,0.515,and 0.586 in the Hits@1,Hits@3 and Hits@10 metrics respectively on the WN18RR dataset and 0.243,0.367 and 0.518 on the FB15K-237 dataset.By incorporating hyperbolic space embedding and hierarchical graph attention,the H2GAT model successfully addresses the limitations of existing hyperbolic knowledge embedding models,exhibiting its competence in knowledge graph completion tasks.

Asymptotic upper bounds for wheel:complete graph Ramsey numbers

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→∞ ).

Vertex-distinguishing E-total Coloring of Complete Bipartite Graph K 7,n when7≤n≤95

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.

Signless Laplacian Characteristic Polynomials of Complete Multipartite Graphs

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.

Signed Roman (Total) Domination Numbers of Complete Bipartite Graphs and Wheels

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.

Vertex-distinguishing IE-total Colorings of Complete Bipartite Graphs K8,n

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.

Distance Integral Complete Multipartite Graphs with s=5, 6

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.

Quantum search of many vertices on the joined complete graph

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.

Bondage and Reinforcement Number of γ_f for Complete Multipartite Graph

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.

COMPLETE MULTIPARTITE DECOMPOSITIONS OF COMPLETE GRAPHS AND COMPLETE n-PARTITE GRAPHS

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.

The Interval Graph Completion Problem for the Complete Multipartite Graphs

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 Decomposition of a Complete Graph with a Hole

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 . A complete graph with a hole, , consists of a complete graph on d vertices, , and a set of independent vertices of size v, V, where each vertex in V is adjacent to each vertex in . When d is even, we give two constructions for the decomposition of a complete graph with a hole into copies of : the Alpha-Delta Construction, and the Alpha-Beta-Delta Construction. By restricting d and v so that , we are able to resolve both of these cases for a subset of using difference methods and 1-factors.

Edge-Transitive Cyclic Covers of Complete Graphs with Prime Power Order

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.

PACKINGS OF THE COMPLETE DIRECTED GRAPH WITH m-CIRCUITS

A packing of the complete directed symmetric graph DK v with m circuits, denoted by ( v,m) DCP, is defined to be a family of arc disjoint m circuits of DK v such that any one arc of DK v \ occurs in at most one m circuit. The packing number P(v,m) is the maximum number of m circuits in such a packing. The packing problem is to determine the value P(v,m) for every integer v≥m. In this paper, the problem is reduced to the case m+6≤v≤2m- 4m-3+12 , for any fixed even integer m≥4 . In particular, the values of P(v,m) are completely determined for m=12 , 14 and 16.

Aquatic Medicine Knowledge Graph Completion Based on Hybrid Convolution

Aquatic medicine knowledge graph is an effective means to realize intelligent aquaculture.Graph completion technology is key to improving the quality of knowledge graph construction.However,the difficulty of semantic discrimination among similar entities and inconspicuous semantic features result in low accuracy when completing aquatic medicine knowledge graph with complex relationships.In this study,an aquatic medicine knowledge graph completion method(TransH+HConvAM)is proposed.Firstly,TransH is applied to split the vector plane between entities and relations,ameliorating the poor completion effect caused by low semantic resolution of entities.Then,hybrid convolution is introduced to obtain the global interaction of triples based on the complete interaction between head/tail entities and relations,which improves the semantic features of triples and enhances the completion effect of complex relationships in the graph.Experiments are conducted to verify the performance of the proposed method.The MR,MRR and Hit@10 of the TransH+HConvAM are found to be 674,0.339,and 0.361,respectively.This study shows that the model effectively overcomes the poor completion effect of complex relationships and improves the construction quality of the aquatic medicine knowledge graph,providing technical support for intelligent aquaculture.