Global ETD Search

1	Improved Bounds on the Domination Number of a Tree Desormeaux, Wyatt J., Haynes, Teresa W., Henning, Michael A. 20 November 2014 (has links) A dominating set in a graph G is a set S of vertices of G such that every vertex not in S is adjacent to a vertex of S. The domination number γ(G) of G is the minimum cardinality of a dominating set of G. The Slater number sl(G) is the smallest integer t such that t added to the sum of the first t terms of the non-increasing degree sequence of G is at least as large as the number of vertices of G. It is well-known that γ(G)≥sl(G). If G has n vertices with minimum degree δ ≥1 and maximum degree Δ, then we show that ⌈n/(δ+1)≤(G)≤n/(δ+1)⌉. Let T be a tree on n≥3 vertices with n1 vertices of degree 1. We prove that γ(T)≤ 3sl(T)-2, and we characterize the trees that achieve equality in this bound. Lemanska (2004) proved that γ(T)≥(n-;bsupesu+2)/3. We improve this result by showing that sl(T)≥(n-;bsupesup+2)/3 and establishing the existence of trees T for which the difference between the Slater number sl(T) and (n-n1+2)/3 is arbitrarily large. Further, the trees T satisfying sl(T)=(n-n1+2)/3 are characterized. degree sequence domination slater number trees Mathematics and Statistics
2	Largest Laplacian Eigenvalue and Degree Sequences of Trees Biyikoglu, Türker, Hellmuth, Marc, Leydold, Josef January 2008 (has links) (PDF) We investigate the structure of trees that have greatest maximum eigenvalue among all trees with a given degree sequence. We show that in such an extremal tree the degree sequence is non-increasing with respect to an ordering of the vertices that is obtained by breadth-first search. This structure is uniquely determined up to isomorphism. We also show that the maximum eigenvalue in such classes of trees is strictly monotone with respect to majorization. (author´s abstract) / Series: Research Report Series / Department of Statistics and Mathematics MSC 05C35, 05C75, 05C05, 05C50
3	Graphs with given degree sequence and maximal spectral radius Biyikoglu, Türker, Leydold, Josef January 2008 (has links) (PDF) We describe the structure of those graphs that have largest spectral radius in the class of all connected graphs with a given degree sequence. We show that in such a graph the degree sequence is non-increasing with respect to an ordering of the vertices induced by breadth-first search. For trees the resulting structure is uniquely determined up to isomorphism. We also show that the largest spectral radius in such classes of trees is strictly monotone with respect to majorization. This paper is the revised final version of the preprint no. 35 of this research report series. (author´s abstract) / Series: Research Report Series / Department of Statistics and Mathematics MSC 05C35, 05C75, 05C05
4	Algebraic Connectivity and Degree Sequences of Trees Biyikoglu, Türker, Leydold, Josef January 2008 (has links) (PDF) We investigate the structure of trees that have minimal algebraic connectivity among all trees with a given degree sequence. We show that such trees are caterpillars and that the vertex degrees are non-decreasing on every path on non-pendant vertices starting at the characteristic set of the Fiedler vector. (author´s abstract) / Series: Research Report Series / Department of Statistics and Mathematics MSC 05C75, 05C05, 05C50
5	Largest Eigenvalues of the Discrete p-Laplacian of Trees with Degree Sequences Biyikoglu, Türker, Hellmuth, Marc, Leydold, Josef January 2009 (has links) (PDF) We characterize trees that have greatest maximum p-Laplacian eigenvalue among all trees with a given degree sequence. We show that such extremal trees can be obtained by breadth-first search where the vertex degrees are non-increasing. These trees are uniquely determined up to isomorphism. Moreover, their structure does not depend on p. / Series: Research Report Series / Department of Statistics and Mathematics MSC 05C35, 05C75, 05C05, 05C50
6	Eccentricity Sequence of 2 Ogbonna, Antoine I. January 2010 (has links) No description available. Mathematics Graphs Eccentricity Eccentricity sequence Degree sequence Degree sums AO-Graphs Connected graphs
7	Faber-Krahn Type Inequalities for Trees Biyikoglu, Türker, Leydold, Josef January 2003 (has links) (PDF) The Faber-Krahn theorem states that among all bounded domains with the same volume in Rn (with the standard Euclidean metric), a ball that has lowest first Dirichlet eigenvalue. Recently it has been shown that a similar result holds for (semi-)regular trees. In this article we show that such a theorem also hold for other classes of (not necessarily non-regular) trees. However, for these new results no couterparts in the world of the Laplace-Beltrami-operator on manifolds are known. / Series: Preprint Series / Department of Applied Statistics and Data Processing MSC 05C35, 05C75, 05C05, 05C50
8	Largest Eigenvalues of Degree Sequences Biyikoglu, Türker, Leydold, Josef January 2006 (has links) (PDF) We show that amongst all trees with a given degree sequence it is a ball where the vertex degrees decrease with increasing distance from its center that maximizes the spectral radius of the graph (i.e., its adjacency matrix). The resulting Perron vector is decreasing on every path starting from the center of this ball. This result it also connected to Faber-Krahn like theorems for Dirichlet matrices on trees. The above result is extended to connected graphs with given degree sequence. Here we give a necessary condition for a graph that has greatest maximum eigenvalue. Moreover, we show that the greatest maximum eigenvalue is monotone on degree sequences with respect to majorization. (author's abstract). Note: There is a more recent version of this paper available: "Graphs with Given Degree Sequence and Maximal Spectral Radius", Research Report Series / Department of Statistics and Mathematics, no. 72. / Series: Research Report Series / Department of Statistics and Mathematics
9	Largest eigenvalues of the discrete p-Laplacian of trees with degree sequences Biyikoglu, Türker, Hellmuth, Marc, Leydold, Josef 08 November 2018 (has links) Trees that have greatest maximum p-Laplacian eigenvalue among all trees with a given degree sequence are characterized. It is shown that such extremal trees can be obtained by breadth-first search where the vertex degrees are non-increasing. These trees are uniquely determined up to isomorphism. Moreover, their structure does not depend on p. info:eu-repo/classification/ddc/005.3 ddc:005.3
10	Degree Sequences, Forcibly Chordal Graphs, and Combinatorial Proof Systems Altomare, Christian J. January 2009 (has links) No description available. Mathematics degree sequence forcibly chordal exclude cycle proof system partial order poset forbidden minor autonomous ausys lexicographic proof blocking Rao's Conjecture well quasi order induced subgraph

Search results