摘要:

AbstractWe look back 250 years to the origins of graph theory when Euler presented a paper on the solution of the Königsberg bridges problem

ISSN:0364-9024    

DOI:10.1002/jgt.3190100305

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

年代:1986

数据来源: WILEY

摘要:

AbstractAn overview of Eulerian graphs is presented. In particular, characterizations of Eulerian graphs and digraphs as well as algorithms for constructing Eulerian circuits are discussed. A solution to the Chinese postman problem is followed by a study of subgraphs and supergraphs of Eulerian graphs. After an introduction to randomly Eulerian graphs and digraphs, we conclude with a summary of a variety of results involving enumeration.

ISSN:0364-9024    

DOI:10.1002/jgt.3190100306

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

年代:1986

数据来源: WILEY

摘要:

AbstractA digraphDwithnvertices is said to be decomposable into a setSof dicycles if every arc ofDis contained in exactly one member ofS. Counterexamples are given to the following conjectures which are generalizations of three well‐known conjectures by G. Hajós, P. Erdős, and P.J. Kelly: (1) [B. Jackson] Every eulerian‐oriented graph is decomposable into at most\documentclass{article}\pagestyle{empty}\begin{document}$ \frac{n}{2} $\end{document}dicycles. (2) [W. Bienia&H. Meyniel] Every eulerian digraph is decomposable into at mostndicycles.Certain observations lead us to make three other conjectures: (a) Every eulerian‐oriented graph is decomposable into at most\documentclass{article}\pagestyle{empty}\begin{document}$ \frac{{2n}}{3} $\end{document}dicycles. (b) Every symmetric digraph withn>1 is decomposable into at most 2n– 3 dicycles. (c) Every eulerian digraph withn>1 is decomposable into at most\documentclass{article}\pagestyle{empty}\begin{document}$ \frac{{8n}}{3} $\end{document}–

ISSN:0364-9024    

DOI:10.1002/jgt.3190100307

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

年代:1986

数据来源: WILEY

摘要:

AbstractAt the occasion of the 250th anniversary of graph theory, we recall some of the basic results and unsolved problems, some of the attractive and surprising methods and results, and some possible future directions in graph theory.

ISSN:0364-9024    

DOI:10.1002/jgt.3190100308

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

年代:1986

数据来源: WILEY

摘要:

AbstractAs graph theory celebrates its 250th anniversary, this essay considers examples of various types of results which the future, it is hoped, will bring.

ISSN:0364-9024    

DOI:10.1002/jgt.3190100309

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

年代:1986

数据来源: WILEY

ISSN:0364-9024    

DOI:10.1002/jgt.3190100310

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

年代:1986

数据来源: WILEY

摘要:

AbstractThe analysis and synthesis of reliable large‐scale networks typically involve a graph theoretic model. We give a survey of the graph theoretic notions which are relevant to the synthesis problem. It is shown how a number of unsolved graph extremal problems relate to the synthesis questio

ISSN:0364-9024    

DOI:10.1002/jgt.3190100311

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

年代:1986

数据来源: WILEY

摘要:

AbstractAfter long implicit use, graph theory is beginning to assume its rightful place in anthropology. Current research on exchange in Oceanian societies (Melanesia, Micronesia, and Polynesia) demonstrates its value for the classification, quantification, simulation, and enumeration of structural forms.

ISSN:0364-9024    

DOI:10.1002/jgt.3190100312

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

年代:1986

数据来源: WILEY

摘要:

AbstractA graphGis ak‐amalgamationof two graphsG1andG2ifG=G1∪G2andG1∩G2is a set ofkvertices. In this paper we show that γ(G) differs from γ(G1) + γ(G2) by at most a quadratic onk, where γ denotes the nonorientable genus of a graph. In the sequel to this paper we show that no such bound holds for the orientable genus ofk‐am

ISSN:0364-9024    

DOI:10.1002/jgt.3190100313

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

年代:1986

数据来源: WILEY

摘要:

AbstractA graphGis ak‐amalgamation of two graphsG1andG2ifG=G1∪G2andG1∩G2is a set ofkvertices. In this paper we construct 3‐amalgamationsGn=Hn∪Hnsuch that γ(Gn) = 5nand γ(Hn) = 3n, where γ denotes the orientable genus of a graph. Thus γ(G1∪G2) may differ from γ(G1) + γ(G2) by an arbitrarily large amount for amalgamations over 3 (or more) vertices. In contrast, an earlier paper shows that the nonorientable genus of ak‐amalgamation differs from the sum of the nonorientable genera of its parts by at m

ISSN:0364-9024    

DOI:10.1002/jgt.3190100314

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

年代:1986

数据来源: WILEY