摘要:

AbstractSome of the early questions concerning the maximum genus of a graph have now been answered. In this paper we survey the progress made on such problems and present some recent results, outlining proofs for some of the major theorems.

ISSN:0364-9024    

DOI:10.1002/jgt.3190030102

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1979

数据来源: WILEY

摘要:

AbstractA constructive characterization of minimally 2‐edge connected graphs, similar to those of Dirac for minimally 2‐connected graphs is gi

ISSN:0364-9024    

DOI:10.1002/jgt.3190030103

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1979

数据来源: WILEY

摘要:

AbstractLetG1,G2…,Gnbe regular graphs andHbe the Cartesian product of these graphs (H=G1×G2× … ×Gn). The following will be proved: If the set {G1,G2…,Gn} has at leat one of the following properties: (*) for at leat oneiϵ {1, 2,…,n}, there exists a 1‐factorization ofGior (**) there exists at least two numbersiandjsuch that 1 ≤i

ISSN:0364-9024    

DOI:10.1002/jgt.3190030104

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1979

数据来源: WILEY

摘要:

AbstractFor a positive integernand a finite groupG, let the symbolse(G, n) andE(G, n) denote, respectively, the smallest and the greatest number of lines among alln‐point graphs with automorphism groupG. We say that the Intermediate Value Theorem (IVT) holds forGandn, if for eachesatisfyinge(G, n)≤e≤E(G, n), there exists ann‐point graph with groupGandelines. The main result of this paper states that for every groupGthe IVT holds for all sufficiently largen. We also prove that the IVT holds for the identity group and alln, and exhibit examples of groups for which the IVT fails to hold for small val

ISSN:0364-9024    

DOI:10.1002/jgt.3190030105

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1979

数据来源: WILEY

摘要:

AbstractThe cochromatic number of a graphG, denoted byz(G), is the minimum number of subsets into which the vertex set ofGcan be partitioned so that each sbuset induces an empty or a complete subgraph ofG. In this paper we introduce the problem of determining for a surfaceS,z(S), which is the maximum cochromatic number among all graphsGthat embed inS. Some general bounds are obtained; for example, it is shown that ifSis orientable of genus at least one, or ifSis nonorientable of genus at least four, thenz(S) is nonorientable of genus at least four, thenz(S)≤χ(S). Here χ(S) denotes the chromatic numberS. Exact results are obtained for the sphere, the Klein bottle, and forS. It is conjectured thatz(S) is equal to the maximumnfor which the graphGn=K1∪K2∪ … ∪K

ISSN:0364-9024    

DOI:10.1002/jgt.3190030106

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1979

数据来源: WILEY

摘要:

AbstractThe voltage graph construction of Gross (orientable case) and Stahl as well as Gross and Tucker (nonorientable case) is extended to the case where the base graph is embedded in a pseudosurface or a generalized pseudosurface. This theory is then applied to produce triangular embeddings ofK4(n); they in turn yield an infinite class of partially balanced incomplete block designs.

ISSN:0364-9024    

DOI:10.1002/jgt.3190030107

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1979

数据来源: WILEY

摘要:

AbstractLetGbe a maximal planar graph withpvertices, and letCk(G) denote the number of cycles of lengthkinG. We first present tight bounds forC3(G) andC4(G) in terms ofp. We then give bounds forCk(G) when 5 ≤k≤ p, and consider in particular bounds forCp(G), in terms ofp. Some conjectures and unsolved problems are sta

ISSN:0364-9024    

DOI:10.1002/jgt.3190030108

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1979

数据来源: WILEY

摘要:

AbstractIn this paper we deduce a necessary and sufficient condition for a line grah to have crossing number 1. In addition, we prove that the line graph of any nonplanar graph has crossing number greater than 2.

ISSN:0364-9024    

DOI:10.1002/jgt.3190030109

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1979

数据来源: WILEY

摘要:

AbstractWe present an algebraic proof of the following result: a set of edges of a multigraphGis contained in some cycle ofGiff the set contains no odd cocycle ofG(“cycle” means here: edge disjoint sum of elementary cycles). As a corollary we obtain the characterization of sub‐Eulerian graphs given by Boesch et al. [The spanning subgraphs of Eulerian grpahs.J. Graph Theory(1) (1977) 7

ISSN:0364-9024    

DOI:10.1002/jgt.3190030110

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1979

数据来源: WILEY

ISSN:0364-9024    

DOI:10.1002/jgt.3190030101

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1979

数据来源: WILEY