This article focuses on properties and structures of trees with maximum mean subtree order in a given family; such trees are called optimal in the family. Our main goal is to describe the structure of optimal trees in and , the families of all trees and caterpillars, respectively, of order . We begin by establishing a powerful tool called the Gluing Lemma, which is used to prove several of our main results. In particular, we show that if is an optimal tree in or for , then every leaf of is adjacent to a vertex of degree at least . We also use the Gluing Lemma to answer an open question of Jamison and to provide a conceptually simple proof of Jamison's result that the path has minimum mean subtree order among all trees of order . We prove that if is optimal in , then the number of leaves in is and that if is optimal in , then the number of leaves in is . Along the way, we describe the asymptotic structure of optimal trees in several narrower families of trees. 相似文献
A digraphD is randomlyn-cyclic (n≥3) if for each vertexv ofD, every (directed) path with initial vertexv and having length at mostn−1 can be extended to av−v (directed) cycle of lengthn. Several results related to and examples of randomlyn-cyclic digraphs are presented. Also, all randomlyn-cyclic digraphs forn=3, 4, and 5 are determined.
Research supported by a Western Michigan University faculty research fellowship.
Research supported in part by a College of Arts and Sciences and Graduate College research assistantship from Western Michigan
University. 相似文献
An overview of Eulerian graphs is presented. In particular, characterizations of Eulerian graphs and digraphs as well as algorithms for constructing Eulerian circuits are discussed. A solution to the Chinese postman problem is followed by a study of subgraphs and supergraphs of Eulerian graphs. After an introduction to randomly Eulerian graphs and digraphs, we conclude with a summary of a variety of results involving enumeration. 相似文献
A connected graph is highly irregular if each of its vertices is adjacent only to vertices with distinct degrees. In this paper we investigate several problems concerning the existence and enumeration of highly irregular graphs as well as their independence numbers, with particular focus on the corresponding problems for highly irregular trees. 相似文献
A Steiner tree for a set S of vertices in a connected graph G is a connected subgraph of G with a smallest number of edges that contains S. The Steiner interval I(S) of S is the union of all the vertices of G that belong to some Steiner tree for S. If S={u,v}, then I(S)=I[u,v] is called the interval between u and v and consists of all vertices that lie on some shortest u-v path in G. The smallest cardinality of a set S of vertices such that ?u,v∈SI[u,v]=V(G) is called the geodetic number and is denoted by g(G). The smallest cardinality of a set S of vertices of G such that I(S)=V(G) is called the Steiner geodetic number of G and is denoted by sg(G). We show that for distance-hereditary graphs g(G)?sg(G) but that g(G)/sg(G) can be arbitrarily large if G is not distance hereditary. An efficient algorithm for finding the Steiner interval for a set of vertices in a distance-hereditary graph is described and it is shown how contour vertices can be used in developing an efficient algorithm for finding the Steiner geodetic number of a distance-hereditary graph. 相似文献
In this paper we consider the concept of the average connectivity of a digraph D defined to be the average, over all ordered pairs (u,v) of vertices of D, of the maximum number of internally disjoint directed u–v paths. We determine sharp bounds on the average connectivity of orientations of graphs in terms of the number of vertices and edges and for tournaments and orientations of trees in terms of their orders. An efficient procedure for finding the maximum average connectivity among all orientations of a tree is described and it is shown that this maximum is always greater than
and at most
. 相似文献
Let G be a connected (di)graph. A vertex w is said to strongly resolve a pair u,v of vertices of G if there exists some shortest u-w path containing v or some shortest v-w path containing u. A set W of vertices is a strong resolving set for G if every pair of vertices of G is strongly resolved by some vertex of W. The smallest cardinality of a strong resolving set for G is called the strong dimension of G. It is shown that the problem of finding the strong dimension of a connected graph can be transformed to the problem of finding the vertex covering number of a graph. Moreover, it is shown that computing this invariant is NP-hard. Related invariants for directed graphs are defined and studied. 相似文献
Those connected graphsG are determined for which there exist nonisomorphic connected graphs of equal size containingG as a unique greatest common subgraph. Analogous results are also obtained for weakly connected and strongly connected digraphs, as well as for induced subgraphs and induced subdigraphs.This research was supported by a Western Michigan University faculty research fellowship.This research was supported in part by a Western Michigan University research assistantship from the Graduate College and the College of Arts and Sciences. 相似文献