اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOn the extremal values of the cyclic continuants of Motzkin and Straus
60
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
In a 1983 paper, G. Ramharter asks what are the extremal arrangements for the cyclic analogues of the regular and semi-regular continuants first introduced by T.S. Motzkin and E.G. Straus in 1956. In this paper we answer this question by showing that for each set $A$ consisting of positive integers $1<a_1<a_2<cdots <a_k$ and a $k$-term partition $P: n_1+n_2 + cdots + n_k=n$, there exists a unique (up to reversal) cyclic word $x$ which maximizes (resp. minimizes) the regular cyclic continuant $K^{circlearrowright}(cdot)$ amongst all cyclic words over $A$ with Parikh vector $(n_1,n_2,ldots,n_k)$. We also show that the same is true for the minimizing arrangement for the semi-regular cyclic continuant $dot K^{circlearrowright}(cdot)$. As in the non-cyclic case, the main difficulty is to find the maximizing arrangement for the semi-regular continuant, which is not unique in general and may depend on the integers $a_1,ldots,a_k$ and not just on their relative order. We show that if a cyclic word $x$ maximizes $dot K^{circlearrowright}(cdot)$ amongst all permutations of $x$, then it verifies a strong combinatorial condition which we call the singular property. We develop an algorithm for constructing all singular cyclic words having a prescribed Parikh vector.
قيم البحث
اقرأ أيضاً
An extension of the well-known Szeged index was introduced recently, named as weighted Szeged index ($textrm{sz}(G)$). This paper is devoted to characterizing the extremal trees and graphs of this new topological invariant. In particular, we proved t
hat the star is a tree having the maximal $textrm{sz}(G)$. Finding a tree with the minimal $textrm{sz}(G)$ is not an easy task to be done. Here, we present the minimal trees up to 25 vertices obtained by computer and describe the regularities which retain in them. Our preliminary computer tests suggest that a tree with the minimal $textrm{sz}(G)$ is also the connected graph of the given order that attains the minimal weighted Szeged index. Additionally, it is proven that among the bipartite connected graphs the complete balanced bipartite graph $K_{leftlfloor n/2rightrfloorleftlceil n/2 rightrceil}$ attains the maximal $textrm{sz}(G)$,. We believe that the $K_{leftlfloor n/2rightrfloorleftlceil n/2 rightrceil}$ is a connected graph of given order that attains the maximum $textrm{sz}(G)$.
For positive integers $w$ and $k$, two vectors $A$ and $B$ from $mathbb{Z}^w$ are called $k$-crossing if there are two coordinates $i$ and $j$ such that $A[i]-B[i]geq k$ and $B[j]-A[j]geq k$. What is the maximum size of a family of pairwise $1$-cross
ing and pairwise non-$k$-crossing vectors in $mathbb{Z}^w$? We state a conjecture that the answer is $k^{w-1}$. We prove the conjecture for $wleq 3$ and provide weaker upper bounds for $wgeq 4$. Also, for all $k$ and $w$, we construct several quite different examples of families of desired size $k^{w-1}$. This research is motivated by a natural question concerning the width of the lattice of maximum antichains of a partially ordered set.
A proper edge-coloring of a graph $G$ with colors $1,ldots,t$ is called an emph{interval cyclic $t$-coloring} if all colors are used, and the edges incident to each vertex $vin V(G)$ are colored by $d_{G}(v)$ consecutive colors modulo $t$, where $d_{
G}(v)$ is the degree of a vertex $v$ in $G$. A graph $G$ is emph{interval cyclically colorable} if it has an interval cyclic $t$-coloring for some positive integer $t$. The set of all interval cyclically colorable graphs is denoted by $mathfrak{N}_{c}$. For a graph $Gin mathfrak{N}_{c}$, the least and the greatest values of $t$ for which it has an interval cyclic $t$-coloring are denoted by $w_{c}(G)$ and $W_{c}(G)$, respectively. In this paper we investigate some properties of interval cyclic colorings. In particular, we prove that if $G$ is a triangle-free graph with at least two vertices and $Gin mathfrak{N}_{c}$, then $W_{c}(G)leq vert V(G)vert +Delta(G)-2$. We also obtain bounds on $w_{c}(G)$ and $W_{c}(G)$ for various classes of graphs. Finally, we give some methods for constructing of interval cyclically non-colorable graphs.
Let $k,l,m,n$, and $mu$ be positive integers. A $mathbb{Z}_mu$--{it scheme of valency} $(k,l)$ and {it order} $(m,n)$ is a $m times n$ array $(S_{ij})$ of subsets $S_{ij} subseteq mathbb{Z}_mu$ such that for each row and column one has $sum_{j=1}^n |
S_{ij}| = k $ and $sum_{i=1}^m |S_{ij}| = l$, respectively. Any such scheme is an algebraic equivalent of a $(k,l)$-semi-regular bipartite voltage graph with $n$ and $m$ vertices in the bipartition sets and voltages coming from the cyclic group $mathbb{Z}_mu$. We are interested in the subclass of $mathbb{Z}_mu$--schemes that are characterized by the property $a - b + c - d; ot equiv ;0$ (mod $mu$) for all $a in S_{ij}$, $b in S_{ih}$, $c in S_{gh}$, and $d in S_{gj}$ where $i,g in {1,...,m}$ and $j,h in {1,...,n}$ need not be distinct. These $mathbb{Z}_mu$--schemes can be used to represent adjacency matrices of regular graphs of girth $ge 5$ and semi-regular bipartite graphs of girth $ge 6$. For suitable $rho, sigma in mathbb{N}$ with $rho k = sigma l$, they also represent incidence matrices for polycyclic $(rho mu_k, sigma mu_l)$ configurations and, in particular, for all known Desarguesian elliptic semiplanes. Partial projective closures yield {it mixed $mathbb{Z}_mu$-schemes}, which allow new constructions for Krv{c}adinacs sporadic configuration of type $(34_6)$ and Balbuenas bipartite $(q-1)$-regular graphs of girth 6 on as few as $2(q^2-q-2)$ vertices, with $q$ ranging over prime powers. Besides some new results, this survey essentially furnishes new proofs in terms of (mixed) $mathbb{Z}_mu$--schemes for ad-hoc constructions used thus far.
A word is square-free if it does not contain any square (a word of the form $XX$), and is extremal square-free if it cannot be extended to a new square-free word by inserting a single letter at any position. Grytczuk, Kordulewski, and Niewiadomski pr
oved that there exist infinitely many ternary extremal square-free words. We establish that there are no extremal square-free words over any alphabet of size at least 17.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
