4-REGULAR GRAPH OF DIAMETER 2

Đỗ Như An, Nguyễn Đình Ái

Abstract


A regular graph is a graph where each vertex has the same degree. A regular graph with vertices of degree k is called a k -regular graph or regular graph of degree k. Let G be a graph, the distance between two vertices in G is the number of edges in a shortest path connecting them. The diameter of G is the greatest distance between any pair of vertices. Let n4 be maximum integer number so that there exists an 4-regular graph on n4 vertices of diameter 2. We prove that n4 = 15.

Keywords


Regular graph; Strongly regular graph; Diameter of graph.



DOI: http://dx.doi.org/10.37569/DalatUniversity.3.2.245(2013)

Refbacks

  • There are currently no refbacks.


Copyright (c) 2013 Đỗ Như An, Nguyễn Đình Ái

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Editorial Office of DLU Journal of Science
Room.15, A25 Building, 01 Phu Dong Thien Vuong Street, Dalat, Lamdong
Email: tapchikhoahoc@dlu.edu.vn - Phone: (+84) 263 3 555 131

Creative Commons License
Based on Open Journal Systems
Developed by Information Technology Department