اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدFurther Results on Pure Summing Registers and Complementary Ones
54
0
0.0
(
0
)
تأليف
Jianrui Xie
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We decide completely the cycle structure of pure summing register (PSR) and complementary summing register (CSR). Based on the state diagram of CSR, we derive an algorithm to generate de Bruijn cycles from CSR inspired by Tuvi Etzions publication in 1984. We then point out the limitation in generalizations of extended representation we use in the algorithm proposed, with a proof of the fact that only PSR and CSR contain pure cycles all dividing n+1.
قيم البحث
اقرأ أيضاً
A emph{proper $t$-edge-coloring} of a graph $G$ is a mapping $alpha: E(G)rightarrow {1,ldots,t}$ such that all colors are used, and $alpha(e) eq alpha(e^{prime})$ for every pair of adjacent edges $e,e^{prime}in E(G)$. If $alpha $ is a proper edge-col
oring of a graph $G$ and $vin V(G)$, then emph{the spectrum of a vertex $v$}, denoted by $Sleft(v,alpha right)$, is the set of all colors appearing on edges incident to $v$. emph{The deficiency of $alpha$ at vertex $vin V(G)$}, denoted by $def(v,alpha)$, is the minimum number of integers which must be added to $Sleft(v,alpha right)$ to form an interval, and emph{the deficiency $defleft(G,alpharight)$ of a proper edge-coloring $alpha$ of $G$} is defined as the sum $sum_{vin V(G)}def(v,alpha)$. emph{The deficiency of a graph $G$}, denoted by $def(G)$, is defined as follows: $def(G)=min_{alpha}defleft(G,alpharight)$, where minimum is taken over all possible proper edge-colorings of $G$. For a graph $G$, the smallest and the largest values of $t$ for which it has a proper $t$-edge-coloring $alpha$ with deficiency $def(G,alpha)=def(G)$ are denoted by $w_{def}(G)$ and $W_{def}(G)$, respectively. In this paper, we obtain some bounds on $w_{def}(G)$ and $W_{def}(G)$. In particular, we show that for any $lin mathbb{N}$, there exists a graph $G$ such that $def(G)>0$ and $W_{def}(G)-w_{def}(G)geq l$. It is known that for the complete graph $K_{2n+1}$, $def(K_{2n+1})=n$ ($nin mathbb{N}$). Recently, Borowiecka-Olszewska, Drgas-Burchardt and Ha{l}uszczak posed the following conjecture on the deficiency of near-complete graphs: if $nin mathbb{N}$, then $def(K_{2n+1}-e)=n-1$. In this paper, we confirm this conjecture.
We provide precise asymptotic estimates for the number of several classes of labelled cubic planar graphs, and we analyze properties of such random graphs under the uniform distribution. This model was first analyzed by Bodirsky et al. (Random Struct
ures Algorithms 2007). We revisit their work and obtain new results on the enumeration of cubic planar graphs and on random cubic planar graphs. In particular, we determine the exact probability of a random cubic planar graph being connected, and we show that the distribution of the number of triangles in random cubic planar graphs is asymptotically normal with linear expectation and variance. To the best of our knowledge, this is the first time one is able to determine the asymptotic distribution for the number of copies of a fixed graph containing a cycle in classes of random planar graphs arising from planar maps.
Let $G$ be a nontrivial connected and vertex-colored graph. A subset $X$ of the vertex set of $G$ is called rainbow if any two vertices in $X$ have distinct colors. The graph $G$ is called emph{rainbow vertex-disconnected} if for any two vertices $x$
and $y$ of $G$, there exists a vertex subset $S$ such that when $x$ and $y$ are nonadjacent, $S$ is rainbow and $x$ and $y$ belong to different components of $G-S$; whereas when $x$ and $y$ are adjacent, $S+x$ or $S+y$ is rainbow and $x$ and $y$ belong to different components of $(G-xy)-S$. Such a vertex subset $S$ is called a emph{rainbow vertex-cut} of $G$. For a connected graph $G$, the emph{rainbow vertex-disconnection number} of $G$, denoted by $rvd(G)$, is the minimum number of colors that are needed to make $G$ rainbow vertex-disconnected. In this paper, we obtain bounds of the rainbow vertex-disconnection number of a graph in terms of the minimum degree and maximum degree of the graph. We give a tighter upper bound for the maximum size of a graph $G$ with $rvd(G)=k$ for $kgeqfrac{n}{2}$. We then characterize the graphs of order $n$ with rainbow vertex-disconnection number $n-1$ and obtain the maximum size of a graph $G$ with $rvd(G)=n-1$. Moreover, we get a sharp threshold function for the property $rvd(G(n,p))=n$ and prove that almost all graphs $G$ have $rvd(G)=rvd(overline{G})=n$. Finally, we obtain some Nordhaus-Gaddum-type results: $n-5leq rvd(G)+rvd(overline{G})leq 2n$ and $n-1leq rvd(G)cdot rvd(overline{G})leq n^2$ for the rainbow vertex-disconnection numbers of nontrivial connected graphs $G$ and $overline{G}$ with order $ngeq 24$.
A close relation between hitting times of the simple random walk on a graph, the Kirchhoff index, resistance-centrality, and related invariants of unicyclic graphs is displayed. Combining with the graph transformations and some other techniques, shar
p upper and lower bounds on the cover cost (resp. reverse cover cost) of a vertex in an $n$-vertex unicyclic graph are determined. All the corresponding extremal graphs are identified, respectively.
In this paper, by the method of comparing coefficients and the inverse technique, we establish the corresponding variate forms of two identities of Andrews and Yee for mock theta functions, as well as a few allied but unusual $q$-series identities. A
mong includes a new Bailey pair from which a product formula of two ${}_2phi_1$ series is derived. Further, we focus on two finite $q$-series summations arising from Andrews and Yees mock theta function identities and expound some recurrence relations and transformation formulas behind them.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
