Cubic graphs
- 1 December 1995
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Computing Surveys
- Vol. 27 (4) , 471-495
- https://doi.org/10.1145/234782.234783
Abstract
This paper is concerned with the subclass of graphs called cubic graphs. We survey these graphsand their history. Several classical graph theory results concerning cubic graphs are explained.Graph theory problems whose solutions on cubic graphs are particularly important or interestingare presented both from the sequential and parallel point of view. A new algorithm is presented forthe maximal matching problem restricted to cubic graphs. Many miscellaneous facts about cubicgraphs are...Keywords
This publication has 37 references indexed in Scilit:
- Some simplified NP-complete graph problemsPublished by Elsevier ,2002
- The lexicographically first maximal subgraph problems:P-completeness andNC algorithmsTheory of Computing Systems, 1989
- The NP-completeness column: An ongoing guideJournal of Algorithms, 1986
- The cube-connected cycles: a versatile network for parallel computationCommunications of the ACM, 1981
- The circuit value problem is log space complete for PACM SIGACT News, 1975
- Regular Graphs with Given Girth and Restricted CircuitsJournal of the London Mathematical Society, 1963
- A non-Hamiltonian planar graphActa Mathematica Hungarica, 1960
- A Minimal Cubic Graph of Girth SevenCanadian Mathematical Bulletin, 1960
- On Hamiltonian CircuitsJournal of the London Mathematical Society, 1946
- On colouring the nodes of a networkMathematical Proceedings of the Cambridge Philosophical Society, 1941