Primitive graphs with given exponents and minimum number of edges |
| |
Authors: | Byeong Moon Kim Byung Chul Song Woonjae Hwang |
| |
Institution: | aDepartment of Mathematics, Kangnung National University, Kangnung 210-702, Republic of Korea bDepartment of Information and Mathematics, Korea University, Jochiwon 339-700, Republic of Korea |
| |
Abstract: | A graph G = (V, E) on n vertices is primitive if there is a positive integer k such that for each pair of vertices u, v of G, there is a walk of length k from u to v. The minimum value of such an integer, k, is the exponent, exp(G), of G. In this paper, we find the minimum number, h(n, k), of edges of a simple graph G on n vertices with exponent k, and we characterize all graphs which have h(n, k) edges when k is 3 or even. |
| |
Keywords: | Primitive graph Exponent |
本文献已被 ScienceDirect 等数据库收录! |
|