摘要:

AbstractThe transmission of a graph or digraphGis the sum of all distances inG.Strict bounds on the transmission are collected and extended for several classes of graphs and digraphs. For example, in the class of 2‐connected or 2‐edge‐connected graphs of order n, the maximal transmission is realized only by the cycleCn.The independence of the transmission on the diameter or radius is shown. Remarks are also given about the NP‐hardness of some related algorithmic p

ISSN:0364-9024    

DOI:10.1002/jgt.3190080102

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

年代:1984

数据来源: WILEY

摘要:

AbstractWe prove a theorem on path systems implying the conjecture of Bollobás that there exists a functionf(k, m)(wherekandmare natural numbers) satisfying the following: For each graphGof minimum degree at leastf(k, m)there exists a graphHof minimum degree at leastksuch thatGcontains the graph obtained fromHby subdividing each edgemtimes

ISSN:0364-9024    

DOI:10.1002/jgt.3190080103

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

年代:1984

数据来源: WILEY

摘要:

AbstractV. K. Proulx has proved that every finite group having a Cayley graph embeddable in the torus is, with four unresolved exceptions, a quotient of a Euclidean space group. It was conjectured that these four unresolved groups are not exceptional, that they in fact are Euclidean space‐group quotients. It is shown here that one is not exceptional, but the other three ar

ISSN:0364-9024    

DOI:10.1002/jgt.3190080104

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

年代:1984

数据来源: WILEY

摘要:

AbstractThis paper presents some conditions under which every automorphism of a graph, embedded on a surface of positive genus, maps face boundaries of the embedding to face boundaries. These results extend a result of Whitney which provides an analogous, but simpler, condition for planar graphs. The new result is applied to graphs on the torus to obtain a classification of many toroidal vertex‐, edge‐, and face‐transitive g

ISSN:0364-9024    

DOI:10.1002/jgt.3190080105

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

年代:1984

数据来源: WILEY

摘要:

AbstractA graph is called decomposable if its vertices can be colored red and blue in such a way that each color appears on at least one vertex but each vertex v has at most one neighbor having a different color from v. We point out a simple and efficient algorithm for recognizing decomposable graphs with maximum degree at most 3 and prove that recognizing decomposable graphs with maximum degree 4 is an NP‐complete proble

ISSN:0364-9024    

DOI:10.1002/jgt.3190080106

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

年代:1984

数据来源: WILEY

摘要:

AbstractLetGbe a group acting symmetrically on a graph Σ, letG1be a subgroup ofGminimal among those that act symmetrically on Σ, and letG2be a subgroup ofG1maximal among those normal subgroups ofG1which contain no member except 1 which fixes a vertex of Σ. The most precise result of this paper is that if Σ has prime valencyp, then either Σ is a bipartite graph orG2acts regularly on Σ orG1|G2is a simple group which acts symmetrically on a graph of valencypwhich can be constructed from Σ and does not have more vertices than Σ. The results on vertex‐transitive groups necessary to establish results like this are also

ISSN:0364-9024    

DOI:10.1002/jgt.3190080107

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

年代:1984

数据来源: WILEY

摘要:

AbstractLetGbe a simple undirected graph which haspvertices and is rooted atx.Informally, the rotation numberh(G, x)of this rooted graph is the minimum number of edges in ap‐vertex graphF, such that for each vertexvofF, there exists a copy ofGinFwith the rootxatv.In this paper, we calculate a lower bound for the rotation number of the graph which is the disjoint union of circuitsCk,Cewhere 4 ⩽k<⩽, give infinite classes where this bound is exact, and obtain classes of rotation numbers for the cas

ISSN:0364-9024    

DOI:10.1002/jgt.3190080108

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

年代:1984

数据来源: WILEY

摘要:

AbstractA formula is found for the maximum number of edges in a graphG⊆K(a, b)which contains no pathP2lforl>c.A similar formula is found for the maximum number of edges inG⊆K(a, b)containing noP2l+ 1forl>c. In addition, all extremal graphs are determi

ISSN:0364-9024    

DOI:10.1002/jgt.3190080109

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

年代:1984

数据来源: WILEY

摘要:

AbstractThe trivalent graph of girth 9 with 58 vertices discovered by N. L. Biggs and M. J. Hoare is not the only graph of this kind.

ISSN:0364-9024    

DOI:10.1002/jgt.3190080110

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

年代:1984

数据来源: WILEY

摘要:

AbstractWe prove that Woodall's and Ghouila‐Houri's conditions on degrees which ensure that a digraph is Hamiltonian, also ensure that it contains the analog of a directed Hamiltonian cycle but with one edge pointing the wrong way; that is, it contains two vertices that are connected in the same direction by both an edge and a Hamiltonian pat

ISSN:0364-9024    

DOI:10.1002/jgt.3190080111

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

年代:1984

数据来源: WILEY