共查询到20条相似文献,搜索用时 31 毫秒
1.
Let be a connected graph with vertex set and edge set . For a subset of , the Steiner distance of is the minimum size of a connected subgraph whose vertex set contains . For an integer with , the Steiner-Wiener index is . In this paper, we introduce some transformations for trees that do not increase their Steiner -Wiener index for . Using these transformations, we get a sharp lower bound on Steiner -Wiener index for trees with given diameter, and obtain the corresponding extremal graph as well. 相似文献
2.
The -restricted arc connectivity of digraphs is a common generalization of the arc connectivity and the restricted arc connectivity. An arc subset of a strong digraph is a -restricted arc cut if has a strong component with order at least such that contains a connected subdigraph with order at least . The -restricted arc connectivity of a digraph is the minimum cardinality over all -restricted arc cuts of .Let be a strong digraph with order and minimum degree . In this paper, we first show that exists if and, furthermore, if , where is the minimum 3-degree of . Next, we prove that if . Finally, we give examples showing that these results are best possible in some sense. 相似文献
3.
Let be a set of at least two vertices in a graph . A subtree of is a -Steiner tree if . Two -Steiner trees and are edge-disjoint (resp. internally vertex-disjoint) if (resp. and ). Let (resp. ) be the maximum number of edge-disjoint (resp. internally vertex-disjoint) -Steiner trees in , and let (resp. ) be the minimum (resp. ) for ranges over all -subset of . Kriesell conjectured that if for any , then . He proved that the conjecture holds for . In this paper, we give a short proof of Kriesell’s Conjecture for , and also show that (resp. ) if (resp. ) in , where . Moreover, we also study the relation between and , where is the line graph of . 相似文献
4.
5.
6.
7.
Let us call a lattice path in from to using , , and steps and never going below the -axis, a -path (of order ). A super -path is a -path which is permitted to go below the -axis. We relate the total number of humps in all of the -paths of order to the number of super -paths, where a hump is defined to be a sequence of steps of the form , . This generalizes recent results concerning the cases when and or . A similar relation may be given involving peaks (consecutive steps of the form ). 相似文献
8.
The -power graph of a graph is a graph with the same vertex set as , in that two vertices are adjacent if and only if, there is a path between them in of length at most . A -tree-power graph is the -power graph of a tree, a -leaf-power graph is the subgraph of some -tree-power graph induced by the leaves of the tree.We show that (1) every -tree-power graph has NLC-width at most and clique-width at most , (2) every -leaf-power graph has NLC-width at most and clique-width at most , and (3) every -power graph of a graph of tree-width has NLC-width at most , and clique-width at most . 相似文献
9.
Irving Dai 《Discrete Mathematics》2018,341(7):1932-1944
The Johnson graphs are a well-known family of combinatorial graphs whose applications and generalizations have been studied extensively in the literature. In this paper, we present a new variant of the family of Johnson graphs, the Full-Flag Johnson graphs, and discuss their combinatorial properties. We show that the Full-Flag Johnson graphs are Cayley graphs on generated by certain well-known classes of permutations and that they are in fact generalizations of permutahedra. We prove a tight bound for the diameter of the Full-Flag Johnson graph FJ and establish recursive relations between FJ and the lower-order Full-Flag Johnson graphs FJ and FJ. We apply this recursive structure to partially compute the spectrum of permutahedra. 相似文献
10.
11.
12.
13.
Bart Litjens 《Discrete Mathematics》2018,341(6):1740-1748
14.
Zoltán Füredi Alexandr Kostochka Ruth Luo Jacques Verstraëte 《Discrete Mathematics》2018,341(5):1253-1263
The Erd?s–Gallai Theorem states that for , any -vertex graph with no cycle of length at least has at most edges. A stronger version of the Erd?s–Gallai Theorem was given by Kopylov: If is a 2-connected -vertex graph with no cycle of length at least , then , where . Furthermore, Kopylov presented the two possible extremal graphs, one with edges and one with edges.In this paper, we complete a stability theorem which strengthens Kopylov’s result. In particular, we show that for odd and all , every -vertex 2-connected graph with no cycle of length at least is a subgraph of one of the two extremal graphs or . The upper bound for here is tight. 相似文献
15.
Let be a finite group, written multiplicatively. The Davenport constant of is the smallest positive integer such that every sequence of with elements has a non-empty subsequence with product . Let be the Dihedral Group of order and be the Dicyclic Group of order . Zhuang and Gao (2005) showed that and Bass (2007) showed that . In this paper, we give explicit characterizations of all sequences of such that and is free of subsequences whose product is 1, where is equal to or for some . 相似文献
16.
Let V be an n-dimensional vector space over the finite field consisting of q elements and let be the Grassmann graph formed by k-dimensional subspaces of V, . Denote by the restriction of to the set of all non-degenerate linear codes. We show that for any two codes the distance in coincides with the distance in only in the case when , i.e. if n is sufficiently large then for some pairs of codes the distances in the graphs and are distinct. We describe one class of such pairs. 相似文献
17.
18.
Let G be a graph with n vertices and edges, and let be the Laplacian eigenvalues of G. Let , where . Brouwer conjectured that for . It has been shown in Haemers et al. [7] that the conjecture is true for trees. We give upper bounds for , and in particular, we show that the conjecture is true for unicyclic and bicyclic graphs. 相似文献
19.
20.