Some New Results About the (d, k) Graph Problem
- 1 August 1982
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-31 (8) , 784-791
- https://doi.org/10.1109/tc.1982.1676084
Abstract
The (d,k) graph problem which is a stiu open extremal problem in graph theory, has received very much attention from many authors due to its theoretic interest, and also due to its possible applications in communication network design. The problem consists in maximizing the number of nodes n of an undirected regular graph (d,k) of degree d and diameter k. In this paper, after a survey of the known results, we present two new families of graphs, and two methods of generating graphs given some existing ones, leading to further substantial improvements of some of the results gathered by Storwick [21] and recently improved by Arden and Lee [3] and also by Imase and Itoh [11].Keywords
This publication has 15 references indexed in Scilit:
- Design to Minimize Diameter on Building-Block NetworkIEEE Transactions on Computers, 1981
- Maximum degree in graphs of diameter 2Networks, 1980
- On some solutions of Ak = dI + λjJournal of Combinatorial Theory, Series A, 1977
- The Indirect Binary n-Cube Microprocessor ArrayIEEE Transactions on Computers, 1977
- Communication networks based on the product graphProceedings of the Institution of Electrical Engineers, 1977
- Regular d-valent graphs of girth 6 and 2(d2−d+1) verticesJournal of Combinatorial Theory, 1970
- On (d, k) GraphsIEEE Transactions on Electronic Computers, 1967
- A Design for (d, k) GraphsIEEE Transactions on Electronic Computers, 1966
- Topological constraints on interconnection-limited logicPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1964
- On Moore Graphs with Diameters 2 and 3IBM Journal of Research and Development, 1960