Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the number of frequency hypercubes $F^n(4;2,2)$
116
0
0.0
(
0
)
Added by
Denis Krotov
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Authors
Minjia Shi
Ask ChatGPT about the research
No Arabic abstract
A frequency $n$-cube $F^n(4;2,2)$ is an $n$-dimensional $4$-by-...-by-$4$ array filled by $0$s and $1$s such that each line contains exactly two $1$s. We classify the frequency $4$-cubes $F^4(4;2,2)$, find a testing set of size $25$ for $F^3(4;2,2)$, and derive an upper bound on the number of $F^n(4;2,2)$. Additionally, for any $n$ greater than $2$, we construct an $F^n(4;2,2)$ that cannot be refined to a latin hypercube, while each of its sub-$F^{n-1}(4;2,2)$ can. Keywords: frequency hypercube, frequency square, latin hypercube, testing set, MDS code
rate research
Read More
A tripartite-circle drawing of a tripartite graph is a drawing in the plane, where each part of a vertex partition is placed on one of three disjoint circles, and the edges do not cross the circles. The tripartite-circle crossing number of a tripartite graph is the minimum number of edge crossings among all tripartite-circle drawings. We determine the tripartite-circle crossing number of $K_{2,2,n}$.
Given an integer $1leq j <n$, define the $(j)$-coloring of a $n$-dimensional hypercube $H_{n}$ to be the $2$-coloring of the edges of $H_{n}$ in which all edges in dimension $i$, $1leq i leq j$, have color $1$ and all other edges have color $2$. Cheng et al. [Proper distance in edge-colored hypercubes, Applied Mathematics and Computation 313 (2017) 384-391.] determined the number of distinct shortest properly colored paths between a pair of vertices for the $(1)$-colored hypercubes. It is natural to consider the number for $(j)$-coloring, $jgeq 2$. In this note, we determine the number of different shortest proper paths in $(j)$-colored hypercubes for arbitrary $j$.
A total coloring of a graph $G$ is a coloring of its vertices and edges such that no adjacent vertices, edges, and no incident vertices and edges obtain the same color. An interval total $t$-coloring of a graph $G$ is a total coloring of $G$ with colors $1,ldots,t$ such that all colors are used, and the edges incident to each vertex $v$ together with $v$ are colored by $d_{G}(v)+1$ consecutive colors, where $d_{G}(v)$ is the degree of a vertex $v$ in $G$. In this paper we prove that all complete multipartite graphs with the same number of vertices in each part are interval total colorable. Moreover, we also give some bounds for the minimum and the maximum span in interval total colorings of these graphs. Next, we investigate interval total colorings of hypercubes $Q_{n}$. In particular, we prove that $Q_{n}$ ($ngeq 3$) has an interval total $t$-coloring if and only if $n+1leq tleq frac{(n+1)(n+2)}{2}$.
In this paper, we give bounds on the dichromatic number $vec{chi}(Sigma)$ of a surface $Sigma$, which is the maximum dichromatic number of an oriented graph embeddable on $Sigma$. We determine the asymptotic behaviour of $vec{chi}(Sigma)$ by showing that there exist constants $a_1$ and $a_2$ such that, $ a_1frac{sqrt{-c}}{log(-c)} leq vec{chi}(Sigma) leq a_2 frac{sqrt{-c}}{log(-c)} $ for every surface $Sigma$ with Euler characteristic $cleq -2$. We then give more explicit bounds for some surfaces with high Euler characteristic. In particular, we show that the dichromatic numbers of the projective plane $mathbb{N}_1$, the Klein bottle $mathbb{N}_2$, the torus $mathbb{S}_1$, and Dycks surface $mathbb{N}_3$ are all equal to $3$, and that the dichromatic numbers of the $5$-torus $mathbb{S}_5$ and the $10$-cross surface $mathbb{N}_{10}$ are equal to $4$. We also consider the complexity of deciding whether a given digraph or oriented graph embedabble in a fixed surface is $k$-dicolourable. In particular, we show that for any surface, deciding whether a digraph embeddable on this surface is $2$-dicolourable is NP-complete, and that deciding whether a planar oriented graph is $2$-dicolourable is NP-complete unless all planar oriented graphs are $2$-dicolourable (which was conjectured by Neumann-Lara).
Let $D$ be an oriented graph. The inversion of a set $X$ of vertices in $D$ consists in reversing the direction of all arcs with both ends in $X$. The inversion number of $D$, denoted by ${rm inv}(D)$, is the minimum number of
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
