The extremal graph of kth upper generalized exponents for a class of primitive graphs

Publication date 29 January 2002

Published in Advances in Mathematics (Beijing) (Search for Journal in Brave)

Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Structural characterization of families of graphs (05C75)

Review text

Graphs discussed in this paper allow loops, but not parallel edges. A graph \(G\) is called primitive if \(G\) is connected and \(G\) contains at least one odd cycle. (A loop is a cycle of length one.) Let \(X\) be a set of vertices of \(G\). Define \(\exp_G(X)\) to be the smallest positive integer \(p\) such that, for any vertex \(y\) of \(G\), there exists a path of length \(p\) from some vertex in \(X\) to \(y\). For a primitive graph \(G\) of order \(n\) and an integer \(k\), \(1\leq k\leq n-1\), let the \(k\)th upper generalized exponents be defined as \(F(G,k)= \max\{\exp_G(X)\mid X\subset V(G), |X|= k\}\). For \(1\leq d\leq n\) and \(2\leq k\leq n-1\), let \(F(n,d,k)\) denote the largest \(k\)th upper generalized exponent of a primitive graph of order \(n\) with \(d\) loops. The values of \(F(n,d,k)\) have already been completely determined. This paper characterizes all extremal graphs that attain the maximum exponents \(F(n,d,k)\).

Recommendations

Cited in

(10)

This page was built for publication: The extremal graph of \(k\)th upper generalized exponents for a class of primitive graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2767410)