The asymptotic properties of the numbers of spanning trees and Eulerian trails in circulant digraphs and graphs are studied. Let $C\left( {p,s_1 ,s_2 , \cdots ,s_k } \right)$ be a directed circulant graph. Let $\left(...The asymptotic properties of the numbers of spanning trees and Eulerian trails in circulant digraphs and graphs are studied. Let $C\left( {p,s_1 ,s_2 , \cdots ,s_k } \right)$ be a directed circulant graph. Let $\left( {C\left( {p,s_1 ,s_2 , \cdots ,s_k } \right)} \right)$ and $\left( {C\left( {p,s_1 ,s_2 , \cdots ,s_k } \right)} \right)$ be the numbers of spanning trees and of Eulerian trails, respectively. Then $$\begin{array}{*{20}c} \begin{gathered} \lim \frac{1}{k}\sqrt[p]{{T\left( {C\left( {p,s_1 ,s_2 , \cdots ,s_k } \right)} \right)}} = 1, \hfill \\ \lim \frac{1}{{k!}}\sqrt[p]{{E\left( {C\left( {p,s_1 ,s_2 , \cdots ,s_k } \right)} \right)}} = 1, \hfill \\ \end{gathered} & {p \to \infty .} \\ \end{array} $$ Furthermore, their line digraph and iterations are dealt with and similar results are obtained for undirected circulant graphs.展开更多
The line graph for the complement of the zero divisor graph for the ring of Gaussian integers modulo n is studied. The diameter, the radius and degree of each vertex are determined. Complete characterization of Hamilt...The line graph for the complement of the zero divisor graph for the ring of Gaussian integers modulo n is studied. The diameter, the radius and degree of each vertex are determined. Complete characterization of Hamiltonian, Eulerian, planer, regular, locally and locally connected is given. The chromatic number when is a power of a prime is computed. Further properties for and are also discussed.展开更多
We obtain a new class of polynomial identities on the ring of n × n matrices over any commutative ring with 1 by using the Swan’s graph theoretic method [1] in the proof of Amitsur-Levitzki theorem. Let be an Eu...We obtain a new class of polynomial identities on the ring of n × n matrices over any commutative ring with 1 by using the Swan’s graph theoretic method [1] in the proof of Amitsur-Levitzki theorem. Let be an Eulerian graph with k vertices and d edges. Further let be an integer and assume that . We prore that is an PI on Mn(C). Standard and Chang [2] -Giambruno-Sehgal [3] polynomial identities are the spectial examples of our conclusions.展开更多
The present research considers the problem of covering a graph with minimal number of trails satisfying the pre-defined local restrictions. The research is devoted to the problem of graph covering by minimal number of...The present research considers the problem of covering a graph with minimal number of trails satisfying the pre-defined local restrictions. The research is devoted to the problem of graph covering by minimal number of trails satisfying some local restrictions. Algotithm of allowed Eulerian cycle construction is considered. The authors showed that it is possible to recognize the system of transitions and solve the problem of constructing the allowable path by linear time. It’s also possible to find allowable Eulerian cycle for Eulerian graph or to proclaim that such a cycle does not exist by the time O(|V(G)|.|E(G)|). All presented algorithms have the software realization.展开更多
Hajos' conjecture asserts that a simple eulerian graph on n vertices can be decomposed into at most n-1/2 circuits. In this paper, we propose a new conjecture which is equivalent to Hajos' conjecture, and show...Hajos' conjecture asserts that a simple eulerian graph on n vertices can be decomposed into at most n-1/2 circuits. In this paper, we propose a new conjecture which is equivalent to Hajos' conjecture, and show that to prove Hajos' conjecture, it is sufficient to prove this new conjecture for 3-connected graphs. Furthermore, a special 3-cut is considered also.展开更多
In this paper, a sufficient condition to partition a travel into circuits of length at least 3 is provided， In particular, a necessary and sufficient condition to partition a planar travel into such circuits, which c...In this paper, a sufficient condition to partition a travel into circuits of length at least 3 is provided， In particular, a necessary and sufficient condition to partition a planar travel into such circuits, which can he verified in polynomial time, is provided，展开更多
基金Project partially supported by the National Natural Science Foundation of China (Grant No. 69673042)Hong Kong CERG (HKUST652/95E)
文摘The asymptotic properties of the numbers of spanning trees and Eulerian trails in circulant digraphs and graphs are studied. Let $C\left( {p,s_1 ,s_2 , \cdots ,s_k } \right)$ be a directed circulant graph. Let $\left( {C\left( {p,s_1 ,s_2 , \cdots ,s_k } \right)} \right)$ and $\left( {C\left( {p,s_1 ,s_2 , \cdots ,s_k } \right)} \right)$ be the numbers of spanning trees and of Eulerian trails, respectively. Then $$\begin{array}{*{20}c} \begin{gathered} \lim \frac{1}{k}\sqrt[p]{{T\left( {C\left( {p,s_1 ,s_2 , \cdots ,s_k } \right)} \right)}} = 1, \hfill \\ \lim \frac{1}{{k!}}\sqrt[p]{{E\left( {C\left( {p,s_1 ,s_2 , \cdots ,s_k } \right)} \right)}} = 1, \hfill \\ \end{gathered} & {p \to \infty .} \\ \end{array} $$ Furthermore, their line digraph and iterations are dealt with and similar results are obtained for undirected circulant graphs.
文摘The line graph for the complement of the zero divisor graph for the ring of Gaussian integers modulo n is studied. The diameter, the radius and degree of each vertex are determined. Complete characterization of Hamiltonian, Eulerian, planer, regular, locally and locally connected is given. The chromatic number when is a power of a prime is computed. Further properties for and are also discussed.
文摘We obtain a new class of polynomial identities on the ring of n × n matrices over any commutative ring with 1 by using the Swan’s graph theoretic method [1] in the proof of Amitsur-Levitzki theorem. Let be an Eulerian graph with k vertices and d edges. Further let be an integer and assume that . We prore that is an PI on Mn(C). Standard and Chang [2] -Giambruno-Sehgal [3] polynomial identities are the spectial examples of our conclusions.
文摘The present research considers the problem of covering a graph with minimal number of trails satisfying the pre-defined local restrictions. The research is devoted to the problem of graph covering by minimal number of trails satisfying some local restrictions. Algotithm of allowed Eulerian cycle construction is considered. The authors showed that it is possible to recognize the system of transitions and solve the problem of constructing the allowable path by linear time. It’s also possible to find allowable Eulerian cycle for Eulerian graph or to proclaim that such a cycle does not exist by the time O(|V(G)|.|E(G)|). All presented algorithms have the software realization.
基金This research is partially supported by the National Postdoctoral Fund of China and Natural Science Foundation of China(No. 10001035) This work was finished while the author was working for Academy of Mathematics and Systems Science, Chinese of Academy
文摘Hajos' conjecture asserts that a simple eulerian graph on n vertices can be decomposed into at most n-1/2 circuits. In this paper, we propose a new conjecture which is equivalent to Hajos' conjecture, and show that to prove Hajos' conjecture, it is sufficient to prove this new conjecture for 3-connected graphs. Furthermore, a special 3-cut is considered also.
基金Supported by National Natural Science Foundation of China(19831080)
文摘In this paper, a sufficient condition to partition a travel into circuits of length at least 3 is provided， In particular, a necessary and sufficient condition to partition a planar travel into such circuits, which can he verified in polynomial time, is provided，
