Almost resolvable Pk-decompositions of complete graphs

An almost P_k-factor of G is a P_k-factor of G - { v } for some vertex v. An almost resolvable P_k-decomposition of λK_n is a partition of the edges of λK_n into almost P_k-factors. We prove that necessary and sufficient conditions for the existence of an almost resolvable P_k-decomposition of λK_n are n ≡ 1 (mod k) and λnk/2 ≡ 0 (mod k ?1).     

Almost resolvable maximum packings of complete graphs with 5-cycles

Let X be the vertex set of K_nA k-cycle packing of K_n is a triple (X,C,L), where C is a collection of edge disjoint k-cycles of K_n and L is the collection of edges of K_n not belonging to any of the k-cycles in C. A k-cycle packing (X,C,L) is called resolvable if C can be partitioned into almost parallel classes. A resolvable maximum k-cycle packing of K_n, denoted by k-RMCP(n), is a resolvable k-cycle packing of K_n, (X,C,L), in which the number of almost parallel classes is as large as possible. Let D(n, k) denote the number of almost parallel classes in a k-RMCP(n). D(n, k) for k = 3, 4 has been decided. When n ≡ k (mod 2k) and k ≡ 1 (mod 2) or n ≡ 1 (mod 2k) and k ∈{6, 8, 10, 14}∪{m: 5≤m≤49, m ≡ 1 (mod 2)}, D(n, k) also has been decided with few possible exceptions. In this paper, we shall decide D(n, 5) for all values of n≥5.     

On 4-semiregular 1-factorizations of complete graphs and complete bipartite graphs

A 4-semiregular 1-factorization is a 1-factorization in which every pair of distinct 1-factors forms a union of 4-cycles. LetK be the complete graphK _2nor the complete bipartite graphK _{n, n} .We prove that there is a 4-semiregular 1-factorization ofK if and only ifn is a power of 2 andn2, and 4-semiregular 1-factorizations ofK are isomorphic, and then we determine the symmetry groups. They are known for the case of the complete graphK _2n ,however, we prove them in a different method.     

On the number of triangular embeddings of complete graphs and complete tripartite graphs

We prove that for every prime number p and odd m>1, as s→∞, there are at least w face 2‐colorable triangular embeddings of K_{w, w, w}, where w = m·p^s. For both orientable and nonorientable embeddings, this result implies that for infinitely many infinite families of z, there is a constant c>0 for which there are at least z nonisomorphic face 2‐colorable triangular embeddings of K_z. © 2011 Wiley Periodicals, Inc. J Graph Theory     

On complete intersection toric ideals of graphs

We study the graphs G for which their toric ideals I _G are complete intersections. In particular, we prove that for a connected graph G such that I _G is a complete intersection all of its blocks are bipartite except for at most two. We prove that toric ideals of graphs which are complete intersections are circuit ideals. In this case, the generators of the toric ideal correspond to even cycles of G except of at most one generator, which corresponds to two edge disjoint odd cycles joint at a vertex or with a path. We prove that the blocks of these graphs satisfy the odd cycle condition. Finally, we characterize all complete intersection toric ideals of graphs which are normal.     

On defining numbers of circular complete graphs

Let d(σ) stand for the defining number of the colouring σ. In this paper we consider and for the onto χ-colourings γ of the circular complete graph K_n,d. In this regard we obtain a lower bound for d^min(K_n,d) and we also prove that this parameter is asymptotically equal to χ-1. Also, we show that when χ?4 and s≠0 then d^max(K_χd-s,d)=χ+2s-3, and, moreover, we prove an inequality relating this parameter to the circular chromatic number for any graph G.     

On the Ramsey multiplicity of complete graphs

We show that, for n large, there must exist at least $$\frac{{n^t }} {{C^{(1 + o(1)t^2 } )}}$$ monochromatic K _t s in any two-colouring of the edges of K _n , where C??2.18 is an explicitly defined constant. The old lower bound, due to Erd?s [2], and based upon the standard bounds for Ramsey??s theorem, is $$\frac{{n^t }} {{4^{(1 + o(1)t^2 } )}}. $$      

On complete graphs with negative r-mean curvature

We generalize Efimov's Theorem for graphs in Euclidean space using the scalar curvature, with an additional hypothesis on the second fundamental form.     

On the seidel integral complete multipartite graphs

For a simple undirected graph G, denote by A(G) the (0,1)-adjacency matrix of G. Let thematrix S(G) = J-I-2A(G) be its Seidel matrix, and let S _G (??) = det(??I-S(G)) be its Seidel characteristic polynomial, where I is an identity matrix and J is a square matrix all of whose entries are equal to 1. If all eigenvalues of S _G (??) are integral, then the graph G is called S-integral. In this paper, our main goal is to investigate the eigenvalues of S _G (??) for the complete multipartite graphs G = $G = K_{n_1 ,n_2 ,...n_t } $ . A necessary and sufficient condition for the complete tripartite graphs K _m,n,t and the complete multipartite graphs to be S-integral is given, respectively.     

On covering graphs by complete bipartite subgraphs

We prove that, if a graph with e edges contains m vertex-disjoint edges, then m²/e complete bipartite subgraphs are necessary to cover all its edges. Similar lower bounds are also proved for fractional covers. For sparse graphs, this improves the well-known fooling set lower bound in communication complexity. We also formulate several open problems about covering problems for graphs whose solution would have important consequences in the complexity theory of boolean functions.     

On the flow numbers of signed complete and complete bipartite graphs

We determine the flow numbers of signed complete and signed complete bipartite graphs.     

Decompositions of complete graphs and complete bipartite graphs into isomorphic supersubdivision graphs

A graph H is called a supersubdivison of a graph G if H is obtained from G by replacing every edge uv of G by a complete bipartite graph K_2,m (m may vary for each edge) by identifying u and v with the two vertices in K_2,m that form one of the two partite sets. We denote the set of all such supersubdivision graphs by SS(G). Then, we prove the following results.

1. Each non-trivial connected graph G and each supersubdivision graph HSS(G) admits an α-valuation. Consequently, due to the results of Rosa (in: Theory of Graphs, International Symposium, Rome, July 1966, Gordon and Breach, New York, Dunod, Paris, 1967, p. 349) and El-Zanati and Vanden Eynden (J. Combin. Designs 4 (1996) 51), it follows that complete graphs K_2cq+1 and complete bipartite graphs K_mq,nq can be decomposed into edge disjoined copies of HSS(G), for all positive integers m,n and c, where q=|E(H)|.

2. Each connected graph G and each supersubdivision graph in SS(G) is strongly n-elegant, where n=|V(G)| and felicitous.

3. Each supersubdivision graph in EASS(G), the set of all even arbitrary supersubdivision graphs of any graph G, is cordial.

Further, we discuss a related open problem.     

On balanced claw designs of complete multi-partite graphs

In this paper, it is shown that a necessary and sufficient condition for the existence of a balanced claw design BCD(m, n, c, λ) of a complete m-partite graph λK_m(n, n,…,n) is λ(m - 1)n ≡ 0 (mod 2c) and (m - 1)n ? c.     

On the complete chromatic number of Halin graphs

ThisresearchissupportedbytheNationalNaturalScienceFoundationofChina.Write.1.IntroductionDefinition1.FOrany3-connectedplanargraphG(V,E,F)withA(G)23,iftheboundaryedgesoffacefowhichisadjacenttotheothersareremoved,itbecomesatree,andthedegreeofeachvertexofV(fo)is3,andthenGiscalledaHalingraph;foiscalledtheouterfaceofG,andtheotherscalledtheinteriorfaces,thevenicesonthefacefoarecalledtheoutervenices,theoillersarecalledtheinterior...ti..,tll.ForanyplanargraphG(V,E,F),f,f'eF,fisadjacenttof'ifan…     

On diagonal resolvable spheres

In this paper we give the complete answer to a question posed by A. Arhangel?skii and prove that the sphere Sⁿ$S^n$ is diagonal resolvable if and only if Sⁿ$S^n$ is an H  -space if and only if n∈{0,1,3,7}$n\in \{0,1,3,7\}$. Moreover, we prove that any upper half even dimensional Q$\mathbb{Q}$-sphere cannot be diagonal resolvable.     

On resolvable primal spaces

A topological space is called resolvable if it is a union of two disjoint dense subsets, and is n-resolvable if it is a union of n mutually disjoint dense subsets. Clearly a resolvable space has no isolated points. If f is a selfmap on X, the sets A?X with f (A)?A are the closed sets of an Alexandroff topology called the primal topology 𝒫(f ) associated with f. We investigate resolvability for primal spaces (X, 𝒫(f)). Our main result is that an Alexandroff space is resolvable if and only if it has no isolated points. Moreover, n-resolvability and other related concepts are investigated for primal spaces.