摘要:

AbstractGraph equations are equations in which the unknowns are graphs. Many problems and results in graph theory can be formulated in terms of graph equations. Here we offer a classification and a large bibliography of graph equations.

ISSN:0364-9024    

DOI:10.1002/jgt.3190030402

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

年代:1979

数据来源: WILEY

摘要:

AbstractAn orthogonal latin square graph (OLSG) is one in which the vertices are latin squares of the same order and on the same symbols, and two vertices are adjacent if and only if the latin squares are orthogonal. IfGis an arbitrary finite graph, we say thatGis realizable as an OLSG if there is an OLSG isomorphic toG. The spectrum ofG[Spec(G)] is defined as the set of all integersnthat there is a realization ofGby latin squares of ordern. The two basic theorems proved here are (1) every graph is realizable and (2) for any graphG, SpecGcontains all but a finite set of integers. A number of examples are given that point to a number of wide open questions. An example of such a question is how to classify the graphs for which a givennlies in the spectrum.

ISSN:0364-9024    

DOI:10.1002/jgt.3190030403

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

年代:1979

数据来源: WILEY

摘要:

AbstractLetGbe an undirected graph without multiple edges and with a loop at every vertex—the set of edges ofGcorresponds to a reflexive and symmetric binary relation on its set of vertices. Thenevery edge‐preserving map of the set of vertices of G to itself fixes an edge[{f(a),f(b)} = {a, b} for some edge (a, b) ofG]if and only if(i)G is connected, (ii)G contains no cycles, and(iii)G contains no infinte paths.The proof is conerned with those subgraphsHof a graphGfor which there is an edge‐preserving mapfof the set of vertices ofGonto the set of vertices ofHand satisfyingf(a) =afor each verte

ISSN:0364-9024    

DOI:10.1002/jgt.3190030404

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

年代:1979

数据来源: WILEY

摘要:

AbstractA graph is locally connected if every neighborthood induces a connected subgraph. We show here that every connected, locally connected graph onp≥ 3 vertices and having no inducedK1,3is Hamiltonian. Several sufficient conditions for a line graph to be Hamiltonian are obtained as corollarie

ISSN:0364-9024    

DOI:10.1002/jgt.3190030405

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

年代:1979

数据来源: WILEY

摘要:

AbstractAll planar connected graphs regular of degree four can be generated from the graph of the octahedron, using four operations.

ISSN:0364-9024    

DOI:10.1002/jgt.3190030406

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

年代:1979

数据来源: WILEY

摘要:

AbstractWe consider the problem of the minimum number of Hamiltonian cycles that could be present in a Hamiltonian maximal planar graph onpvertices. In particular, we construct ap‐vertex maximal planar graph containing exactly four Hamiltonian cycles for everyp≥ 12. We also prove that every 4‐connected maximal planar graph onpvertices contains at leastp/(log2p) Hamiltonian c

ISSN:0364-9024    

DOI:10.1002/jgt.3190030407

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

年代:1979

数据来源: WILEY

摘要:

AbstractBerge conjectured that every finite simple 4‐regular graphGcontains a 3‐regular subgraph. We prove that this conjecture is true if the cyclic edge connectivity λc(G) ofGis at least 10. Also we prove that ifGis a smallest counterexample, then λc(G) is either 6

ISSN:0364-9024    

DOI:10.1002/jgt.3190030408

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

年代:1979

数据来源: WILEY

摘要:

AbstractIn this paper, we prove the following result: Every graph obtained by connecting (with any number of edges) two vertex‐disjoint upper‐embeddable graphs graphs with even Betti number is upper‐embed

ISSN:0364-9024    

DOI:10.1002/jgt.3190030409

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

年代:1979

数据来源: WILEY

摘要:

AbstractChartrand and Stewart have shown that the line graph of ann‐connected graph is itselfn‐connected. This paper shows that for every pair of integersm>n>1 there is a graph of point connectivitynwhose line graph has point connectivitym. The corresponding question for line connectivity is also resol

ISSN:0364-9024    

DOI:10.1002/jgt.3190030410

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

年代:1979

数据来源: WILEY

摘要:

AbstractIt is shown that the minimum number of vertices in a triangle‐free 5‐chromatic graph is at least

ISSN:0364-9024    

DOI:10.1002/jgt.3190030411

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

年代:1979

数据来源: WILEY