共查询到20条相似文献,搜索用时 15 毫秒
1.
The looseness of a triangular embedding of a complete graph in a closed surface is the minimum integer m such that for every assignment of m colors to the vertices of the embedding (such that all m colors are used) there is a face incident with vertices of three distinct colors. In this paper we show that for every p?3 there is a nonorientable triangular embedding of a complete graph with looseness at least p. 相似文献
2.
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 Kw, w, w, where w = m·ps. 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 Kz. © 2011 Wiley Periodicals, Inc. J Graph Theory 相似文献
3.
We prove a theorem that for an integer s?0, if 12s+7 is a prime number, then the number of nonisomorphic face 3-colorable nonorientable triangular embeddings of Kn, where n=(12s+7)(6s+7), is at least . By some number-theoretic arguments there are an infinite number of integers s satisfying the hypothesis of the theorem. The theorem is the first known example of constructing at least 2αn?+o(n?), ?>1, nonisomorphic nonorientable triangular embeddings of Kn for n=6t+1, . To prove the theorem, we use a new approach to constructing nonisomorphic triangular embeddings of complete graphs. The approach combines a cut-and-paste technique and the index one current graph technique. A new connection between Steiner triple systems and constructing triangular embeddings of complete graphs is given. 相似文献
4.
Diane M. Donovan Mike J. Grannell Terry S. Griggs James G. Lefevre Thomas McCourt 《组合设计杂志》2011,19(1):16-27
It is shown that for every admissible order v for which a cyclic Steiner triple system exists, there exists a biembedding of a cyclic Steiner quasigroup of order v with a copy of itself. Furthermore, it is shown that for each n≥2 the projective Steiner quasigroup of order 2n?1 has a biembedding with a copy of itself. © 2010 Wiley Periodicals, Inc. J Combin Designs 19:16‐27, 2010 相似文献
5.
M.J. Grannell 《Discrete Mathematics》2006,306(6):600-606
Orientable triangular embeddings of the complete tripartite graph Kn,n,n correspond to biembeddings of Latin squares. We show that if n is prime there are at least enlnn-n(1+o(1)) nonisomorphic biembeddings of cyclic Latin squares of order n. If n=kp, where p is a large prime number, then the number of nonisomorphic biembeddings of cyclic Latin squares of order n is at least eplnp-p(1+lnk+o(1)). Moreover, we prove that for every n there is a unique regular triangular embedding of Kn,n,n in an orientable surface. 相似文献
6.
Lindner's conjecture that any partial Steiner triple system of order u can be embedded in a Steiner triple system of order v if and is proved. © 2008 Wiley Periodicals, Inc. J Combin Designs 17: 63–89, 2009 相似文献
7.
M.J. Grannell 《Discrete Mathematics》2009,309(9):2847-2860
We give a characterization of a current assignment on the bipartite Möbius ladder graph with 2n+1 rungs. Such an assignment yields an index one current graph with current group Z12n+7 that generates an orientable face 2-colorable triangular embedding of the complete graph K12n+7 or, equivalently, an orientable biembedding of two cyclic Steiner triple systems of order 12n+7. We use our characterization to construct Skolem sequences that give rise to such current assignments. These produce many nonisomorphic orientable biembeddings of cyclic Steiner triple systems of order 12n+7. 相似文献
8.
Suh-Ryung Kim 《Discrete Applied Mathematics》2008,156(18):3522-3524
For a graph G, it is known to be a hard problem to compute the competition number k(G) of the graph G in general. In this paper, we give an explicit formula for the competition numbers of complete tripartite graphs. 相似文献
9.
There are many results on the maximum genus, among which most are written for the existence of values of such embeddings,
and few attention has been paid to the estimation of such embeddings and their applications. In this paper we study the number
of maximum genus embeddings for a graph and find an exponential lower bound for such numbers. Our results show that in general
case, a simple connected graph has exponentially many distinct maximum genus embeddings. In particular, a connected cubic
graph G of order n always has at least distinct maximum genus embeddings, where α and m denote, respectively, the number of inner vertices and odd components of an optimal tree T. What surprise us most is that such two extremal embeddings (i.e., the maximum genus embeddings and the genus embeddings)
are sometimes closely related with each other. In fact, as applications, we show that for a sufficient large natural number
n, there are at least many genus embeddings for complete graph K
n
with n ≡ 4, 7, 10 (mod12), where C is a constance depending on the value of n of residue 12. These results improve the bounds obtained by Korzhik and Voss and the methods used here are much simpler and
straight.
This work was supported by the National Natural Science Foundation of China (Grant No. 10671073), Science and Technology commission
of Shanghai Municipality (Grant No. 07XD14011) and Shanghai Leading Academic Discipline Project (Grant No. B407) 相似文献
10.
In this paper, it will be shown that the isomorphism classes of regular orientable embeddings of the complete bipartite graph Kn,n are in one‐to‐one correspondence with the permutations on n elements satisfying a given criterion, and the isomorphism classes of them are completely classified when n is a product of any two (not necessarily distinct) prime numbers. For other n, a lower bound of the number of those isomorphism classes of Kn,n is obtained. As a result, many new regular orientable embeddings of the complete bipartite graph are constructed giving an answer of Nedela‐?koviera's question raised in 12 . © 2005 Wiley Periodicals, Inc. J Graph Theory 相似文献
11.
Vladimir P. Korzhik 《Discrete Mathematics》1998,190(1-3):149-162
The author has proposed methods of constructing index 2 and 3 current graphs generating triangular embeddings of graphs Kn−Km with unboundedly large m (as n increases). As a result, triangular embeddings of graphs of many families of graphs Kn−Km with unboundedly large m were constructed. The paper gives a survey of these results and a short explanation of the methods. 相似文献
12.
A Steiner quadruple system of order 2n is Semi‐Boolean (SBQS(2n) in short) if all its derived triple systems are isomorphic to the point‐line design associated with the projective geometry PG(n?1, 2). We prove by means of explicit constructions that for any n, up to isomorphism, there exist at least 2? 3(n?4)/2? regular and resolvable SBQS(2n). © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 229–239, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10050 相似文献
13.
WANG FuRong & DU ShaoFei School of Information Beijing Wuzi University Beijing China School of Mathematical Sciences Capital Normal University Beijing 《中国科学 数学(英文版)》2011,(2)
In [J. Algeb. Combin. 19(2004), 123-141], Du et al. classified the orientable regular embeddings of connected simple graphs of order pq for any two primes p and q. In this paper, we shall classify the nonorientable regular embeddings of these graphs, where p ≠ q. Our classification depends on the classification of primitive permutation groups of degree p and degree pq but is independent of the classification of the arc-transitive graphs of order pq. 相似文献
14.
15.
For all odd integers n ≥ 1, let Gn denote the complete graph of order n, and for all even integers n ≥ 2 let Gn denote the complete graph of order n with the edges of a 1‐factor removed. It is shown that for all non‐negative integers h and t and all positive integers n, Gn can be decomposed into h Hamilton cycles and t triangles if and only if nh + 3t is the number of edges in Gn. © 2004 Wiley Periodicals, Inc. 相似文献
16.
17.
In this paper, we describe the generation of all nonorientable triangular embeddings of the complete graphs K12 and K13. (The 59 nonisomorphic orientable triangular embeddings of K12 were found in 1996 by Altshuler, Bokowski, and Schuchert, and K13 has no orientable triangular embeddings.) There are 182,200 nonisomorphic nonorientable triangular embeddings for K12, and 243,088,286 for K13. Triangular embeddings of complete graphs are also known as neighborly maps and are a type of twofold triple system. We also use methods of Wilson to provide an upper bound on the number of simple twofold triple systems of order n, and thereby on the number of triangular embeddings of Kn. We mention an application of our results to flexibility of embedded graphs. © 2005 Wiley Periodicals, Inc. J Combin Designs 相似文献
18.
Byung Kee Kim 《Journal of Applied Mathematics and Computing》2004,14(1-2):185-191
Given a connected graphG, we say that a setC ?V(G) is convex inG if, for every pair of verticesx, y ∈ C, the vertex set of everyx-y geodesic inG is contained inC. The convexity number ofG is the cardinality of a maximal proper convex set inG. In this paper, we show that every pairk, n of integers with 2 ≤k ≤ n?1 is realizable as the convexity number and order, respectively, of some connected triangle-free graph, and give a lower bound for the convexity number ofk-regular graphs of ordern withn>k+1. 相似文献
19.
In this paper, we present a conjecture that is a common generalization of the Doyen–Wilson Theorem and Lindner and Rosa's intersection theorem for Steiner triple systems. Given u, v ≡ 1,3 (mod 6), u < v < 2u + 1, we ask for the minimum r such that there exists a Steiner triple system such that some partial system can be completed to an STS , where |?| = r. In other words, in order to “quasi‐embed” an STS(u) into an STS(v), we must remove r blocks from the small system, and this r is the least such with this property. One can also view the quantity (u(u ? 1)/6) ? r as the maximum intersection of an STS(u) and an STS(v) with u < v. We conjecture that the necessary minimum r = (v ? u) (2u + 1 ? v)/6 can be achieved, except when u = 6t + 1 and v = 6t + 3, in which case it is r = 3t for t ≠ 2, or r = 7 when t = 2. Using small examples and recursion, we solve the cases v ? u = 2 and 4, asymptotically solve the cases v ? u = 6, 8, and 10, and further show for given v ? u > 2 that an asymptotic solution exists if solutions exist for a run of consecutive values of u (whose required length is no more than v ? u). Some results are obtained for v close to 2u + 1 as well. The cases where ≈ 3u/2 seem to be the hardest. © 2004 Wiley Periodicals, Inc. 相似文献
20.
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. 相似文献