اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدSpanning tree enumeration via triangular rank-one perturbations of graph Laplacians
93
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We present new short proofs of known spanning tree enumeration formulae for threshold and Ferrers graphs by showing that the Laplacian matrices of such graphs admit triangular rank-one perturbations. We then characterize the set of graphs whose Laplacian matrices admit triangular rank-one perturbations as the class of special 2-threshold graphs, introduced by Hung, Kloks, and Villaamil. Our work introduces (1) a new characterization of special 2-threshold graphs that generalizes the characterization of threshold graphs in terms of isolated and dominating vertices, and (2) a spanning tree enumeration formula for special 2-threshold graphs that reduces to the aforementioned formulae for threshold and Ferrers graphs. We consider both unweighted and weighted spanning tree enumeration.
قيم البحث
اقرأ أيضاً
In this paper, we consider various classes of polyiamonds that are animals residing on the triangular lattice. By careful analyses through certain layer-by-layer decompositions and cell pruning/growing arguments, we derive explicit forms for the gene
rating functions of the number of nonempty translation-invariant baryiamonds (bargraphs in the triangular lattice), column-convex polyiamonds, and convex polyiamonds with respect to their perimeter. In particular, we show that the number of (A) baryiamonds of perimeter $n$ is asymptotically $$frac{(xi+1)^2sqrt{xi^4+xi^3-2xi+1}}{2sqrt{pi n^3}}xi^{-n-2},$$ where $xi$ is a root of a certain explicit polynomial of degree 5. (B) column-convex polyiamonds of perimeter $n$ is asymptotic to $$frac{(17997809sqrt{17}+3^3cdot13cdot175463)sqrt{95sqrt{17}-119}}{2^7cdot43^2cdot 89^2sqrt{6pi n^3}}left(frac{3+sqrt{17}}{2}right)^{n-1}.$$ (C) convex polyiamonds of perimeter $n$ is asymptotic to $$frac{1280}{441sqrt{3pi n^3}}3^n.$$
In enumerative combinatorics, it is often a goal to enumerate both labeled and unlabeled structures of a given type. The theory of combinatorial species is a novel toolset which provides a rigorous foundation for dealing with the distinction between
labeled and unlabeled structures. The cycle index series of a species encodes the labeled and unlabeled enumerative data of that species. Moreover, by using species operations, we are able to solve for the cycle index series of one species in terms of other, known cycle indices of other species. Section 3 is an exposition of species theory and Section 4 is an enumeration of point-determining bipartite graphs using this toolset. In Section 5, we extend a result about point-determining graphs to a similar result for point-determining {Phi}-graphs, where {Phi} is a class of graphs with certain properties. Finally, Appendix A is an expository on species computation using the software Sage [9] and Appendix B uses Sage to calculate the cycle index series of point-determining bipartite graphs.
We study resonances generated by rank one perturbations of selfadjoint operators with eigenvalues embedded in the continuous spectrum. Instability of these eigenvalues is analyzed and almost exponential decay for the associated resonant states is exh
ibited. We show how these results can be applied to Sturm-Liouville operators. Main tools are the Aronszajn-Donoghue theory for rank one perturbations, a reduction process of the resolvent based on Feshbach-Livsic formula, the Fermi golden rule and a careful analysis of the Fourier transform of quasi-Lorentzian functions. We relate these results to sojourn time estimates and spectral concentration phenomena
We consider $m$-divisible non-crossing partitions of ${1,2,ldots,mn}$ with the property that for some $tleq n$ no block contains more than one of the first $t$ integers. We give a closed formula for the number of multi-chains of such non-crossing par
titions with prescribed number of blocks. Building on this result, we compute Chapotons $M$-triangle in this setting and conjecture a combinatorial interpretation for the $H$-triangle. This conjecture is proved for $m=1$.
Given a set of points in the Euclidean plane, the Euclidean textit{$delta$-minimum spanning tree} ($delta$-MST) problem is the problem of finding a spanning tree with maximum degree no more than $delta$ for the set of points such the sum of the total
length of its edges is minimum. Similarly, the Euclidean textit{$delta$-minimum bottleneck spanning tree} ($delta$-MBST) problem, is the problem of finding a degree-bounded spanning tree for a set of points in the plane such that the length of the longest edge is minimum. When $delta leq 4$, these two problems may yield disjoint sets of optimal solutions for the same set of points. In this paper, we perform computational experiments to compare the accuracies of a variety of heuristic and approximation algorithms for both these problems. We develop heuristics for these problems and compare them with existing algorithms. We also describe a new type of edge swap algorithm for these problems that outperforms all the algorithms we tested.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
