اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدA median-type condition for graph tiling
120
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Komlos [Tiling Turan theorems, Combinatorica, 20,2 (2000), 203{218] determined the asymptotically optimal minimum degree condition for covering a given proportion of vertices of a host graph by vertex-disjoint copies of a fixed graph. We show that the minimum degree condition can be relaxed in the sense that we require only a given fraction of vertices to have the prescribed degree.
قيم البحث
اقرأ أيضاً
Quasi-median graphs are a tool commonly used by evolutionary biologists to visualise the evolution of molecular sequences. As with any graph, a quasi-median graph can contain cut vertices, that is, vertices whose removal disconnect the graph. These v
ertices induce a decomposition of the graph into blocks, that is, maximal subgraphs which do not contain any cut vertices. Here we show that the special structure of quasi-median graphs can be used to compute their blocks without having to compute the whole graph. In particular we present an algorithm that, for a collection of $n$ aligned sequences of length $m$, can compute the blocks of the associated quasi-median graph together with the information required to correctly connect these blocks together in run time $mathcal O(n^2m^2)$, independent of the size of the sequence alphabet. Our primary motivation for presenting this algorithm is the fact that the quasi-median graph associated to a sequence alignment must contain all most parsimonious trees for the alignment, and therefore precomputing the blocks of the graph has the potential to help speed up any method for computing such trees.
We say a graph $G$ has a Hamiltonian path if it has a path containing all vertices of $G$. For a graph $G$, let $sigma_2(G)$ denote the minimum degree sum of two nonadjacent vertices of $G$; restrictions on $sigma_2(G)$ are known as Ore-type conditio
ns. Given an integer $tgeq 5$, we prove that if a connected graph $G$ on $n$ vertices satisfies $sigma_2(G)>{t-3over t-2}n$, then $G$ has either a Hamiltonian path or an induced subgraph isomorphic to $K_{1, t}$. Moreover, we characterize all $n$-vertex graphs $G$ where $sigma_2(G)={t-3over t-2}n$ and $G$ has neither a Hamiltonian path nor an induced subgraph isomorphic to $K_{1, t}$. This is an analogue of a recent result by Mom`ege, who investigated the case when $t=4$.
A graph $G$ is $k$-path-coverable if its vertex set $V(G)$ can be covered by $k$ or fewer vertex disjoint paths. In this paper, using the $Q$-index of a connected graph $G$, we present a tight sufficient condition for $G$ with fixed minimum degree and large order to be $k$-path-coverable.
We study the generating function of descent numbers for the permutations with descent pairs of prescribed parities, the distribution of which turns out to be a refinement of median Genocchi numbers. We prove the $gamma$-positivity for the polynomial
and derive the generating function for the $gamma$-vectors, expressed in the form of continued fraction. We also come up with an artificial statistic that gives a $q$-analogue of the $gamma$-positivity for the permutations with descents only allowed from an odd value to an odd value.
In this paper a closed form expression for the number of tilings of an $ntimes n$ square border with $1times 1$ and $2times1$ cuisenaire rods is proved using a transition matrix approach. This problem is then generalised to $mtimes n$ rectangular bor
ders. The number of distinct tilings up to rotational symmetry is considered, and closed form expressions are given, in the case of a square border and in the case of a rectangular border. Finally, the number of distinct tilings up to dihedral symmetry is considered, and a closed form expression is given in the case of a square border.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
