The nonorientable genus of the symmetric quadripartite graph

The nonorientable genus of K_4(n) is shown to satisfy:

$\text{γ}\text{(K}{}_{\mathrm{4(n)}}\text{)=2(n?1)}{}^2\text{for n ? 3}$

,

$\text{γ}\text{(K}{}_{\mathrm{4(2)}}\text{)=3,}\text{γ}\text{(K}{}_4\text{(1))=1}$

.     

Path-path Ramsey-type numbers for the complete bipartite graph

For a fixed pair of integers r, s ≥ 2, all positive integers m and n are determined which have the property that if the edges of K_m,n (a complete bipartite graph with parts n and m) are colored with two colors, then there will always exist a path with r vertices in the first color or a path with s vertices in the second color.     

Covering a graph by complete bipartite graphs

We prove the following theorem: the edge set of every graph G on n vertices can be partitioned into the disjoint union of complete bipartite graphs such that each vertex is contained by at most c(n/log n) of the bipartite graphs.     

Nonorientable genus of nearly complete bipartite graphs

LetG(m, n, k), m, n≥3,k≤min(m, n), be the graph obtained from the complete bipartite graphK _m,n by deleting an arbitrary set ofk independent edges, and let $$f(m,n,k) = [(m - 2)(n - 2) - k]/2.$$ It is shown that the nonorientable genus \(\tilde \gamma \) (G(m, n, k)) of the graphG(m, n, k) is equal to the upper integer part off(m, n, k), except in trivial cases wheref(m, n, k)≤0 and possibly in some extreme cases, the graphsG(k, k, k) andG(k + 1,k, k). These cases are also discussed, obtaining some positive and some negative results. In particular, it is shown thatG(5, 4, 4) andG(5, 5, 5) have no nonorientable quadrilateral embedding.     

Minimum genus embeddings of the complete graph

In this paper,the problem of construction of exponentially many minimum genus embeddings 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 K_(12s+8) in orientable surfaces,which show that there are at least 10/3×(200/9)~s distinct minimum genus embeddings for K_(12s+8) in orientable surfaces.We have also proved that K_(12s+8) has at least 10/3×(200/9)~s distinct minimum genus embeddings in non-orientable surfaces.     

Asymptotic bounds for some bipartite graph: complete graph Ramsey numbers

The Ramsey number r(H,K_n) is the smallest integer N so that each graph on N vertices that fails to contain H as a subgraph has independence number at least n. It is shown that r(K_2,m,K_n)(m−1+o(1))(n/log n)² and r(C_2m,K_n)c(n/log n)^m/(m−1) for m fixed and n→∞. Also r(K_2,n,K_n)=Θ(n³/log² n) and .     

Universality among graphs omitting a complete bipartite graph

For cardinals λ,κ,θ we consider the class of graphs of cardinality λ which has no subgraph which is (κ,θ)-complete bipartite graph. The question is whether in such a class there is a universal one under (weak) embedding. We solve this problem completely under GCH. Under various assumptions mostly related to cardinal arithmetic we prove non-existence of universals for this problem. We also look at combinatorial properties useful for those problems concerning κ-dense families.     

Blocks and the nonorientable genus of graphs

Examples are given to show that the nonorientable genus of a graph is not additive over its blocks. A nonorientable analog for the Battle, Harary, Kodama, and Youngs Theorem is proved; this completely determines the nonorientable genus of a graph in terms of its blocks. It is also shown that one of the above counterexamples has the minimum possible order.     

The nonorientable genus is additive

A graph G is a k-amalgamation of two graphs G₁ and G₂ if G = G₁ ∪ G₂ and G₁ ∩G₂ is a set of k vertices. In this paper we show that γ(G) differs from γ(G₁) + γ(G₂) by at most a quadratic on k, where γ denotes the nonorientable genus of a graph. In the sequel to this paper we show that no such bound holds for the orientable genus of k-amalgamations.     

Packing four copies of a tree into a complete bipartite graph

Czechoslovak Mathematical Journal - In considering packing three copies of a tree into a complete bipartite graph, H. Wang (2009) gives a conjecture: For each tree T of order n and each integer k...     

Thep-intersection number of a complete bipartite graph and orthogonal double coverings of a clique

Thep-intersection graph of a collection of finite sets {S _i } _i=1 ⁿ is the graph with vertices 1, ...,n such thati, j are adjacent if and only if |S _i S _j |p. Thep-intersection number of a graphG, herein denoted _p (G), is the minimum size of a setU such thatG is thep-intersection graph of subsets ofU. IfG is the complete bipartite graphK _n,n andp2, then _p (K _{n, n} )(n ²+(2p–1)n)/p. Whenp=2, equality holds if and only ifK _n has anorthogonal double covering, which is a collection ofn subgraphs ofK _n , each withn–1 edges and maximum degree 2, such that each pair of subgraphs shares exactly one edge. By construction,K _n has a simple explicit orthogonal double covering whenn is congruent modulo 12 to one of {1, 2, 5, 7, 10, 11}.Research supported in part by ONR Grant N00014-5K0570.     

The nonorientable genus of the join of two cycles

In this paper, we show that the nonorientable genus of Cm ＋ Cn, the join of two cycles Cm and Cn, is equal to [（（m-2）（n-2））/2] if m = 3, n ≡ 1 （mod 2）, or m ≥ 4, n ≥ 4, （m, n） （4, 4）. We determine that the nonorientable genus of C4 ＋C4 is 3, and that the nonorientable genus of C3 ＋Cn is n/2 if n ≡ 0 （mod 2）. Our results show that a minimum nonorientable genus embedding of the complete bipartite graph Km,n cannot be extended to an embedding of the join of two cycles without increasing the genus of the surface.     

s‐Regular cubic graphs as coverings of the complete bipartite graph K3,3

A graph is s‐regular if its automorphism group acts freely and transitively on the set of s‐arcs. An infinite family of cubic 1‐regular graphs was constructed in [10], as cyclic coverings of the three‐dimensional Hypercube. In this paper, we classify the s‐regular cyclic coverings of the complete bipartite graph K_3,3 for each ≥ 1 whose fibre‐preserving automorphism subgroups act arc‐transitively. As a result, a new infinite family of cubic 1‐regular graphs is constructed. © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 101–112, 2004     

Unbalanced bipartite factorizations of complete bipartite graphs

We construct a new infinite family of factorizations of complete bipartite graphs by factors all of whose components are copies of a (fixed) complete bipartite graph K_p,q. There are simple necessary conditions for such factorizations to exist. The family constructed here demonstrates sufficiency in many new cases. In particular, the conditions are always sufficient when q=p+1.