اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدA combinatorial statistic for labeled threshold graphs
100
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Consider the collection of hyperplanes in $mathbb{R}^n$ whose defining equations are given by ${x_i + x_j = 0mid 1leq i<jleq n}$. This arrangement is called the threshold arrangement since its regions are in bijection with labeled threshold graphs on $n$ vertices. Zaslavskys theorem implies that the number of regions of this arrangement is the sum of coefficients of the characteristic polynomial of the arrangement. In the present article we give a combinatorial meaning to these coefficients as the number of labeled threshold graphs with a certain property, thus answering a question posed by Stanley.
قيم البحث
اقرأ أيضاً
Tuza famously conjectured in 1981 that in a graph without k+1 edge-disjoint triangles, it suffices to delete at most 2k edges to obtain a triangle-free graph. The conjecture holds for graphs with small treewidth or small maximum average degree, inclu
ding planar graphs. However, for dense graphs that are neither cliques nor 4-colorable, only asymptotic results are known. Here, we confirm the conjecture for threshold graphs, i.e. graphs that are both split graphs and cographs, and for co-chain graphs with both sides of the same size divisible by 4.
A non-commutative, planar, Hopf algebra of rooted trees was proposed in L. Foissy, Bull. Sci. Math. 126 (2002) 193-239. In this paper we propose such a non-commutative Hopf algebra for graphs. In order to define a non-commutative product we use a qua
ntum field theoretical (QFT) idea, namely the one of introducing discrete scales on each edge of the graph (which, within the QFT framework, corresponds to energy scales of the associated propagators).
A vertex coloring of a graph $G$ is called distinguishing if no non-identity automorphisms of $G$ can preserve it. The distinguishing number of $G$, denoted by $D(G)$, is the minimum number of colors required for such coloring. The distinguishing thr
eshold of $G$, denoted by $theta(G)$, is the minimum number $k$ such that every $k$-coloring of $G$ is distinguishing. In this paper, we study $theta(G)$, find its relation to the cycle structure of the automorphism group of $G$ and prove that $theta(G)=2$ if and only if $G$ is isomorphic to $K_2$ or $overline{K_2}$. Moreover, we study graphs that have the distinguishing threshold equal to 3 or more and prove that $theta(G)=D(G)$ if and only if $G$ is asymmetric, $K_n$ or $overline{K_n}$. Finally, we consider the graphs in the Johnson scheme for their distinguishing numbers and thresholds.
We focus on counting the number of labeled graphs on $n$ vertices and treewidth at most $k$ (or equivalently, the number of labeled partial $k$-trees), which we denote by $T_{n,k}$. So far, only the particular cases $T_{n,1}$ and $T_{n,2}$ had been s
tudied. We show that $$ left(c cdot frac{kcdot 2^k cdot n}{log k} right)^n cdot 2^{-frac{k(k+3)}{2}} cdot k^{-2k-2} leq T_{n,k} leq left(k cdot 2^k cdot nright)^n cdot 2^{-frac{k(k+1)}{2}} cdot k^{-k}, $$ for $k > 1$ and some explicit absolute constant $c > 0$. The upper bound is an immediate consequence of the well-known number of labeled $k$-trees, while the lower bound is obtained from an explicit algorithmic construction. It follows from this construction that both bounds also apply to graphs of pathwidth and proper-pathwidth at most $k$.
A split graph is a graph whose vertices can be partitioned into a clique and a stable set. We investigate the combinatorial species of split graphs, providing species-theoretic generalizations of enumerative results due to Bina and Pv{r}ibil (2015),
Cheng, Collins, and Trenk (2016), and Collins and Trenk (2018). In both the labeled and unlabeled cases, we give asymptotic results on the number of split graphs, of unbalanced split graphs, and of bicolored graphs, including proving the conjecture of Cheng, Collins, and Trenk (2016) that almost all split graphs are balanced.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
