Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the extremal values of the cyclic continuants of Motzkin and Straus
60
0
0.0
(
0
)
Added by
Alessandro De Luca
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 that 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$-crossing 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 proved 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
