Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA median-type condition for graph tiling
120
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 vertices 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 conditions. 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 borders. 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
