اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدFeedback vertex number of Sierpi{n}ski-type graphs
92
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
The feedback vertex number $tau(G)$ of a graph $G$ is the minimum number of vertices that can be deleted from $G$ such that the resultant graph does not contain a cycle. We show that $tau(S_p^n)=p^{n-1}(p-2)$ for the Sierpi{n}ski graph $S_p^n$ with $pgeq 2$ and $ngeq 1$. The generalized Sierpi{n}ski triangle graph $hat{S_p^n}$ is obtained by contracting all non-clique edges from the Sierpi{n}ski graph $S_p^{n+1}$. We prove that $tau(hat{S}_3^n)=frac {3^n+1} 2=frac{|V(hat{S}_3^n)|} 3$, and give an upper bound for $tau(hat{S}_p^n)$ for the case when $pgeq 4$.
قيم البحث
اقرأ أيضاً
Phase transition of the classical Ising model on the Sierpi{n}ski carpet, which has the fractal dimension $log_3^{~} 8 approx 1.8927$, is studied by an adapted variant of the higher-order tensor renormalization group method. The second-order phase tr
ansition is observed at the critical temperature $T_{rm c}^{~} = 1.4783(1)$. Position dependence of local functions is studied by means of impurity tensors, which are inserted at different locations on the fractal lattice. The critical exponent $beta$ associated with the local magnetization varies by two orders of magnitude, depending on lattice locations, whereas $T_{rm c}^{~}$ is not affected.
In this paper, we investigate the existence of Sierpi{n}ski numbers and Riesel numbers as binomial coefficients. We show that for any odd positive integer $r$, there exist infinitely many Sierpi{n}ski numbers and Riesel numbers of the form $binom{k}{
r}$. Let $S(x)$ be the number of positive integers $r$ satisfying $1leq rleq x$ for which $binom{k}{r}$ is a Sierpi{n}ski number for infinitely many $k$. We further show that the value $S(x)/x$ gets arbitrarily close to 1 as $x$ tends to infinity. Generalizations to base $a$-Sierpi{n}ski numbers and base $a$-Riesel numbers are also considered. In particular, we prove that there exist infinitely many positive integers $r$ such that $binom{k}{r}$ is simultaneously a base $a$-Sierpi{n}ski and base $a$-Riesel number for infinitely many $k$.
By a finite type-graph we mean a graph whose set of vertices is the set of all $k$-subsets of $[n]={1,2,ldots, n}$ for some integers $nge kge 1$, and in which two such sets are adjacent if and only if they realise a certain order type specified in ad
vance. Examples of such graphs have been investigated in a great variety of contexts in the literature with particular attention being paid to their chromatic number. In recent joint work with Tomasz {L}uczak, two of the authors embarked on a systematic study of the chromatic numbers of such type-graphs, formulated a general conjecture determining this number up to a multiplicative factor, and proved various results of this kind. In this article we fully prove this conjecture.
Given a graph $H$ and a positive integer $n,$ the Tur{a}n number of $H$ for the order $n,$ denoted ${rm ex}(n,H),$ is the maximum size of a simple graph of order $n$ not containing $H$ as a subgraph. The book with $p$ pages, denoted $B_p$, is the gra
ph that consists of $p$ triangles sharing a common edge. Bollob{a}s and ErdH{o}s initiated the research on the Tur{a}n number of book graphs in 1975. The two numbers ${rm ex}(p+2,B_p)$ and ${rm ex}(p+3,B_p)$ have been determined by Qiao and Zhan. In this paper we determine the numbers ${rm ex}(p+4,B_p),$ ${rm ex}(p+5,B_p)$ and ${rm ex}(p+6,B_p),$ and characterize the corresponding extremal graphs for the numbers ${rm ex}(n,B_p)$ with $n=p+2,,p+3,,p+4,,p+5.$
A $t$-bar visibility representation of a graph assigns each vertex up to $t$ horizontal bars in the plane so that two vertices are adjacent if and only if some bar for one vertex can see some bar for the other via an unobstructed vertical channel of
positive width. The least $t$ such that $G$ has a $t$-bar visibility representation is the bar visibility number of $G$, denoted by $b(G)$. We show that if $H$ is a spanning subgraph of $G$, then $b(H)le b(G)+1$. It follows that $b(G)le lceil n/6rceil+1$ when $G$ is an $n$-vertex graph. This improves the upper bound obtained by Chang et al. (SIAM J. Discrete Math. 18 (2004) 462).
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
