Premium
On large (Δ, 6)‐Graphs
Author(s) -
Martí J. Gómez
Publication year - 2005
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20075
Subject(s) - bipartite graph , combinatorics , mathematics , cograph , graph , pathwidth , 1 planar graph , line graph , discrete mathematics
In this article, a new method is proposed for obtaining large‐diameter 6 graphs by replacing some vertices of a Moore bipartite diameter 6 graph by complete K h graphs. These complete graphs are joined to the remaining nonmodified graph and to each other by means of new edges. More precisely, these new edges are those of a bipartite diameter 3 graph, together with some appropriate extra edges. The degree and the diameter of the graph so constructed coincide with those of the original one. The construction put forward here gives rise to some of the largest known diameter 6 graphs. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 46(2), 82–87 2005