共查询到20条相似文献,搜索用时 0 毫秒
1.
We prove that, for a certain positive constant a and for an infinite set of values of n, the number of nonisomorphic triangular embeddings of the complete graph Kn is at least nan2. A similar lower bound is also given, for an infinite set of values of n, on the number of nonisomorphic triangular embeddings of the complete regular tripartite graph Kn,n,n. 相似文献
2.
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 相似文献
3.
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. 相似文献
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.
完全3-部图K_(1,10,n)的交叉数 总被引:1,自引:0,他引:1
在上世纪五十年代初,Zarankiewicz猜想完全2-部图Km,m(m≤n)的交叉数为[m/2][m-1/2][n/2][n-1/2](对任意实数x,[x]表示不超过x的最大整数),目前只证明了当m ≤ 6时,Zarankiewicz猜想是正确的.假定Zarankiewicz猜想对m=11的情形成立,本文确定完全3-部图K1,10,n的交叉数. 相似文献
6.
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. 相似文献
7.
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. 相似文献
8.
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. 相似文献
9.
The complete tripartite graph K
n,n,n has 3n
2 edges. For any collection of positive integers x
1, x
2,...,x
m with
and x
i ⩾ 3 for 1 ⩽ i ⩽ m, we exhibit an edge-disjoint decomposition of K
n,n,n into closed trails (circuits) of lengths x
1, x
2,..., x
m.
Supported by Ministry of Education of the Czech Republic as project LN00A056. 相似文献
10.
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. 相似文献
11.
On the complete chromatic number of Halin graphs 总被引:8,自引:0,他引:8
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… 相似文献
12.
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) 相似文献
13.
We prove that, with the single exception of the 2‐group C, the Cayley table of each Abelian group appears in a face 2‐colorable triangular embedding of a complete regular tripartite graph in an orientable surface. © 2009 Wiley Periodicals, Inc. J Combin Designs 18: 71–83, 2010 相似文献
14.
An oriented tripartite graph is the result of assigning a direction to each edge of a simple tripartite graph. For any vertex
x in an oriented tripartite graph D(U,V,W), let d
x
+ and d
x
− denote the outdegree and indegree respectively of x. Define $
a_{u_i } = d_{u_i }^ + - d_{u_i }^ - , b_{v_j } = d_{v_j }^ + - d_{v_j }^ -
$
a_{u_i } = d_{u_i }^ + - d_{u_i }^ - , b_{v_j } = d_{v_j }^ + - d_{v_j }^ -
and $
c_{w_k } = d_{w_k }^ + - d_{w_k }^ -
$
c_{w_k } = d_{w_k }^ + - d_{w_k }^ -
as the imbalances of the vertices u
i
in U, v
j
in V and w
k
in W respectively. In this paper, we obtain criteria for sequences of integers to be the imbalances of some oriented tripartite
graph. 相似文献
15.
Some necessary conditions on a graph which has the same chromatic polynomial as the complete tripartite graph Km,n,r are developed. Using these, we obtain the chromatic equivalence classes for Km,n,n (where 1≤m≤n) and Km1,m2,m3 (where |mi−mj|≤3). In particular, it is shown that (i) Km,n,n (where 2≤m≤n) and (ii) Km1,m2,m3 (where |mi−mj|≤3, 2≤mi,i=1,2,3) are uniquely determined by their chromatic polynomials. The result (i), proved earlier by Liu et al. [R.Y. Liu, H.X. Zhao, C.Y. Ye, A complete solution to a conjecture on chromatic uniqueness of complete tripartite graphs, Discrete Math. 289 (2004) 175-179], answers a conjecture (raised in [G.L. Chia, B.H. Goh, K.M. Koh, The chromaticity of some families of complete tripartite graphs (In Honour of Prof. Roberto W. Frucht), Sci. Ser. A (1988) 27-37 (special issue)]) in the affirmative, while result (ii) extends a result of Zou [H.W. Zou, On the chromatic uniqueness of complete tripartite graphs Kn1,n2,n3 J. Systems Sci. Math. Sci. 20 (2000) 181-186]. 相似文献
16.
17.
18.
A certain recursive construction for biembeddings of Latin squares has played a substantial role in generating large numbers of nonisomorphic triangular embeddings of complete graphs. In this article, we prove that, except for the groups and C 4 , each Latin square formed from the Cayley table of an Abelian group appears in a biembedding in which the second Latin square has a transversal. Such biembeddings may then be freely used as ingredients in the recursive construction. Copyright © 2011 Wiley Periodicals, Inc. J Combin Designs 20:81‐88, 2012 相似文献
19.
20.
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 相似文献