Since many large graphs are composed from some existing smaller graphs by using graph operations, say, the Cartesian product, the Lexicographic product and the Strong product. Many properties of such large graphs are ...Since many large graphs are composed from some existing smaller graphs by using graph operations, say, the Cartesian product, the Lexicographic product and the Strong product. Many properties of such large graphs are closely related to those of the corresponding smaller ones. In this short note, we give some properties of the Strong product of vertex-transitive graphs. In particular, we show that the Strong product of Cayley graphs is still a Cayley graph.展开更多
Let γ^＊（D） denote the twin domination number of digraph D and let Di× D 2 denote the strong product of Di and D 2. In this paper, we obtain that the twin domination number of strong product of tw...Let γ^＊（D） denote the twin domination number of digraph D and let Di× D 2 denote the strong product of Di and D 2. In this paper, we obtain that the twin domination number of strong product of two directed cycles of length at least 2. Furthermore, we give a lower bound of the twin domination number of strong product of two digraphs, and prove that the twin domination number of strong product of the complete digraph and any digraph D equals the twin domination number of D.展开更多
The products of graphs discussed in this paper are the following four kinds: the Cartesian product of graphs, the tensor product of graphs, the lexicographic product of graphs and the strong direct product of graphs. ...The products of graphs discussed in this paper are the following four kinds: the Cartesian product of graphs, the tensor product of graphs, the lexicographic product of graphs and the strong direct product of graphs. It is proved that:① If the graphs G 1 and G 2 are the connected graphs, then the Cartesian product, the lexicographic product and the strong direct product in the products of graphs, are the path positive graphs. ② If the tensor product is a path positive graph if and only if the graph G 1 and G 2 are the connected graphs, and the graph G 1 or G 2 has an odd cycle and max{ λ 1μ 1,λ nμ m}≥2 in which λ 1 and λ n [ or μ 1 and μ m] are maximum and minimum characteristic values of graph G 1 [ or G 2 ], respectively.展开更多
In this paper we define direct product of graphs and give a recipe for obtaining probability of observing particle on vertices in the continuous-time classical and quantum random walk. In the recipe, the probability o...In this paper we define direct product of graphs and give a recipe for obtaining probability of observing particle on vertices in the continuous-time classical and quantum random walk. In the recipe, the probability of observing particle on direct product of graph is obtained by multiplication of probability on the corresponding to sub-graphs, where this method is useful to determining probability of walk on compficated graphs. Using this method, we calculate the probability of Continuous-time classical and quantum random walks on many of finite direct product Cayley graphs （complete cycle, complete Kn, charter and n-cube）. Also, we inquire that the classical state the stationary uniform distribution is reached as t→∞ but for quantum state is not always satisfied.展开更多
Let D be a finite simple directed graph with vertex set V(D) and arc set A(D). A function ?is called a signed dominating function (SDF) if ?for each vertex . The weight ?of f is defined by . The signed domination numb...Let D be a finite simple directed graph with vertex set V(D) and arc set A(D). A function ?is called a signed dominating function (SDF) if ?for each vertex . The weight ?of f is defined by . The signed domination number of a digraph D is . Let Cm × Cn denotes the cartesian product of directed cycles of length m and n. In this paper, we determine the exact values of gs(Cm × Cn) for m = 8, 9, 10 and arbitrary n. Also, we give the exact value of gs(Cm × Cn) when m, ?(mod 3) and bounds for otherwise.展开更多
Let j, k and m be three positive integers, a circular m-L（j, k）-labeling of a graph G is a mapping f： V（G）→{0, 1, …, m-1}such that f（u）-f（v）m≥j if u and v are adjacent, and f（u）-f（v）m≥k if u and v are...Let j, k and m be three positive integers, a circular m-L（j, k）-labeling of a graph G is a mapping f： V（G）→{0, 1, …, m-1}such that f（u）-f（v）m≥j if u and v are adjacent, and f（u）-f（v）m≥k if u and v are at distance two,where a-bm=min{a-b,m-a-b}. The minimum m such that there exists a circular m-L（j, k）-labeling of G is called the circular L（j, k）-labeling number of G and is denoted by σj, k（G）. For any two positive integers j and k with j≤k,the circular L（j, k）-labeling numbers of trees, the Cartesian product and the direct product of two complete graphs are determined.展开更多
Let γ f(G) and γ~t f(G) be the fractional domination number and fractional total domination number of a graph G respectively. Hare and Stewart gave some exact fractional domination number of P n...Let γ f(G) and γ~t f(G) be the fractional domination number and fractional total domination number of a graph G respectively. Hare and Stewart gave some exact fractional domination number of P n×P m (grid graph) with small n and m . But for large n and m , it is difficult to decide the exact fractional domination number. Motivated by this, nearly sharp upper and lower bounds are given to the fractional domination number of grid graphs. Furthermore, upper and lower bounds on the fractional total domination number of strong direct product of graphs are given.展开更多
Let R be a commutative ring with non-zero identity. The cozero-divisor graph of R, denoted by , is a graph with vertices in , which is the set of all non-zero and non-unit elements of R, and two distinct vertices a an...Let R be a commutative ring with non-zero identity. The cozero-divisor graph of R, denoted by , is a graph with vertices in , which is the set of all non-zero and non-unit elements of R, and two distinct vertices a and b in are adjacent if and only if and . In this paper, we investigate some combinatorial properties of the cozero-divisor graphs and such as connectivity, diameter, girth, clique numbers and planarity. We also study the cozero-divisor graphs of the direct products of two arbitrary commutative rings.展开更多
A vertex cycle cover of a digraph <i>H</i> is a collection C = {<em>C</em><sub>1</sub>, <em>C</em><sub>2</sub>, …, <em>C</em><sub><em&g...A vertex cycle cover of a digraph <i>H</i> is a collection C = {<em>C</em><sub>1</sub>, <em>C</em><sub>2</sub>, …, <em>C</em><sub><em>k</em></sub>} of directed cycles in <i>H</i> such that these directed cycles together cover all vertices in <i>H</i> and such that the arc sets of these directed cycles induce a connected subdigraph of <i>H</i>. A subdigraph <i>F</i> of a digraph <i>D</i> is a circulation if for every vertex in <i>F</i>, the indegree of <em>v</em> equals its out degree, and a spanning circulation if <i>F</i> is a cycle factor. Define <i>f</i> (<i>D</i>) to be the smallest cardinality of a vertex cycle cover of the digraph obtained from <i>D</i> by contracting all arcs in <i>F</i>, among all circulations <i>F</i> of <i>D</i>. Adigraph <i>D</i> is supereulerian if <i>D</i> has a spanning connected circulation. In [International Journal of Engineering Science Invention, 8 (2019) 12-19], it is proved that if <em>D</em><sub>1</sub> and <em>D</em><sub>2</sub> are nontrivial strong digraphs such that <em>D</em><sub>1</sub> is supereulerian and <em>D</em><sub>2</sub> has a cycle vertex cover C’ with |C’| ≤ |<em>V</em> (<em>D</em><sub>1</sub>)|, then the Cartesian product <em>D</em><sub>1</sub> and <em>D</em><sub>2</sub> is also supereulerian. In this paper, we prove that for strong digraphs<em> D</em><sub>1</sub> and <em>D</em><sub>2</sub>, if for some cycle factor <em>F</em><sub>1</sub> of <em>D</em><sub>1</sub>, the digraph formed from <em>D</em><sub>1</sub> by contracting arcs in F1 is hamiltonian with <i>f</i> (<i>D</i><sub>2</sub>) not bigger than |<em>V</em> (<em>D</em><sub>1</sub>)|, then the strong product <em>D</em><sub>1</sub> and <em>D</em><sub>2</sub> is supereulerian.展开更多
A strong product graph is denoted by G_(1)■G_(2),where G_(1) and G_(2) are called its factor graphs.This paper gives the range of the minimum strong radius of the strong product graph.And using the relationship betwe...A strong product graph is denoted by G_(1)■G_(2),where G_(1) and G_(2) are called its factor graphs.This paper gives the range of the minimum strong radius of the strong product graph.And using the relationship between the cartesian product graph G_(1)■G_(2) and the strong product graph G_(1)■G_(2),another different upper bound of the minimum strong radius of the strong product graph is given.展开更多
Based on the key function of version management in PDM system, this paper discusses the function and the realization of version management and the transitions of version states with a workflow. A directed aeyclic grap...Based on the key function of version management in PDM system, this paper discusses the function and the realization of version management and the transitions of version states with a workflow. A directed aeyclic graph is used to describe a version model. Three storage modes of the directed acyelic graph version model in the database, the bumping block and the PDM working memory are presented and the conversion principle of these three modes is given. The study indicates that building a dynamic product structure configuration model based on versions is the key to resolve the problem. Thus a version model of single product object is built. Then the version management model in product structure configuration is built and the application of version management of PDM syster is presented as a case.展开更多
In this paper, the cycle structures for directed graphs on surfaces are studied. If G is a strongly connected graph, C is a ∏-contractible directed cycle of G, then both of Int（C,∏） and Ext（C,∏） are strongly co...In this paper, the cycle structures for directed graphs on surfaces are studied. If G is a strongly connected graph, C is a ∏-contractible directed cycle of G, then both of Int（C,∏） and Ext（C,∏） are strongly connected graph; the dimension of cycles space of G is identified. If G is a strongly connected graph, then the structure of MCB in G is unique. Let G be a strongly connected graph, if G has been embedded in orientable surface Sg with fw（G） ≥ 2（fw（G） is the face-width of G）, then any cycle base of G must contain at least 2g noncontractible directed cycles; if G has been embedded in non-orientable surface Ng, then any cycle base of G must contain at least g noncontractible directed cycles.展开更多
基金Supported by the National Natural Science Foundation of China(61164005,11161037,11101232,61440005,11461054)Supported by the Program for Changjiang Scholars and Innovative Research Team in Universities(IRT1068)+1 种基金Supported by the Research Fund for the Chunhui Program of Ministry of Education of China(Z2014022)Supported by the Nature Science Foundation from Qinghai Province(2014-ZJ-721,2014-ZJ-907,2015-ZJ-905)
文摘Since many large graphs are composed from some existing smaller graphs by using graph operations, say, the Cartesian product, the Lexicographic product and the Strong product. Many properties of such large graphs are closely related to those of the corresponding smaller ones. In this short note, we give some properties of the Strong product of vertex-transitive graphs. In particular, we show that the Strong product of Cayley graphs is still a Cayley graph.
基金The NSF(11301450,61363020,11226294)of Chinathe Youth Science and Technology Education Project(2014731003)of Xinjiang Province
文摘Let γ^＊（D） denote the twin domination number of digraph D and let Di× D 2 denote the strong product of Di and D 2. In this paper, we obtain that the twin domination number of strong product of two directed cycles of length at least 2. Furthermore, we give a lower bound of the twin domination number of strong product of two digraphs, and prove that the twin domination number of strong product of the complete digraph and any digraph D equals the twin domination number of D.
文摘The products of graphs discussed in this paper are the following four kinds: the Cartesian product of graphs, the tensor product of graphs, the lexicographic product of graphs and the strong direct product of graphs. It is proved that:① If the graphs G 1 and G 2 are the connected graphs, then the Cartesian product, the lexicographic product and the strong direct product in the products of graphs, are the path positive graphs. ② If the tensor product is a path positive graph if and only if the graph G 1 and G 2 are the connected graphs, and the graph G 1 or G 2 has an odd cycle and max{ λ 1μ 1,λ nμ m}≥2 in which λ 1 and λ n [ or μ 1 and μ m] are maximum and minimum characteristic values of graph G 1 [ or G 2 ], respectively.
文摘In this paper we define direct product of graphs and give a recipe for obtaining probability of observing particle on vertices in the continuous-time classical and quantum random walk. In the recipe, the probability of observing particle on direct product of graph is obtained by multiplication of probability on the corresponding to sub-graphs, where this method is useful to determining probability of walk on compficated graphs. Using this method, we calculate the probability of Continuous-time classical and quantum random walks on many of finite direct product Cayley graphs （complete cycle, complete Kn, charter and n-cube）. Also, we inquire that the classical state the stationary uniform distribution is reached as t→∞ but for quantum state is not always satisfied.
文摘Let D be a finite simple directed graph with vertex set V(D) and arc set A(D). A function ?is called a signed dominating function (SDF) if ?for each vertex . The weight ?of f is defined by . The signed domination number of a digraph D is . Let Cm × Cn denotes the cartesian product of directed cycles of length m and n. In this paper, we determine the exact values of gs(Cm × Cn) for m = 8, 9, 10 and arbitrary n. Also, we give the exact value of gs(Cm × Cn) when m, ?(mod 3) and bounds for otherwise.
基金The National Natural Science Foundation of China(No.10971025)
文摘Let j, k and m be three positive integers, a circular m-L（j, k）-labeling of a graph G is a mapping f： V（G）→{0, 1, …, m-1}such that f（u）-f（v）m≥j if u and v are adjacent, and f（u）-f（v）m≥k if u and v are at distance two,where a-bm=min{a-b,m-a-b}. The minimum m such that there exists a circular m-L（j, k）-labeling of G is called the circular L（j, k）-labeling number of G and is denoted by σj, k（G）. For any two positive integers j and k with j≤k,the circular L（j, k）-labeling numbers of trees, the Cartesian product and the direct product of two complete graphs are determined.
文摘Let γ f(G) and γ~t f(G) be the fractional domination number and fractional total domination number of a graph G respectively. Hare and Stewart gave some exact fractional domination number of P n×P m (grid graph) with small n and m . But for large n and m , it is difficult to decide the exact fractional domination number. Motivated by this, nearly sharp upper and lower bounds are given to the fractional domination number of grid graphs. Furthermore, upper and lower bounds on the fractional total domination number of strong direct product of graphs are given.
文摘Let R be a commutative ring with non-zero identity. The cozero-divisor graph of R, denoted by , is a graph with vertices in , which is the set of all non-zero and non-unit elements of R, and two distinct vertices a and b in are adjacent if and only if and . In this paper, we investigate some combinatorial properties of the cozero-divisor graphs and such as connectivity, diameter, girth, clique numbers and planarity. We also study the cozero-divisor graphs of the direct products of two arbitrary commutative rings.
文摘A vertex cycle cover of a digraph <i>H</i> is a collection C = {<em>C</em><sub>1</sub>, <em>C</em><sub>2</sub>, …, <em>C</em><sub><em>k</em></sub>} of directed cycles in <i>H</i> such that these directed cycles together cover all vertices in <i>H</i> and such that the arc sets of these directed cycles induce a connected subdigraph of <i>H</i>. A subdigraph <i>F</i> of a digraph <i>D</i> is a circulation if for every vertex in <i>F</i>, the indegree of <em>v</em> equals its out degree, and a spanning circulation if <i>F</i> is a cycle factor. Define <i>f</i> (<i>D</i>) to be the smallest cardinality of a vertex cycle cover of the digraph obtained from <i>D</i> by contracting all arcs in <i>F</i>, among all circulations <i>F</i> of <i>D</i>. Adigraph <i>D</i> is supereulerian if <i>D</i> has a spanning connected circulation. In [International Journal of Engineering Science Invention, 8 (2019) 12-19], it is proved that if <em>D</em><sub>1</sub> and <em>D</em><sub>2</sub> are nontrivial strong digraphs such that <em>D</em><sub>1</sub> is supereulerian and <em>D</em><sub>2</sub> has a cycle vertex cover C’ with |C’| ≤ |<em>V</em> (<em>D</em><sub>1</sub>)|, then the Cartesian product <em>D</em><sub>1</sub> and <em>D</em><sub>2</sub> is also supereulerian. In this paper, we prove that for strong digraphs<em> D</em><sub>1</sub> and <em>D</em><sub>2</sub>, if for some cycle factor <em>F</em><sub>1</sub> of <em>D</em><sub>1</sub>, the digraph formed from <em>D</em><sub>1</sub> by contracting arcs in F1 is hamiltonian with <i>f</i> (<i>D</i><sub>2</sub>) not bigger than |<em>V</em> (<em>D</em><sub>1</sub>)|, then the strong product <em>D</em><sub>1</sub> and <em>D</em><sub>2</sub> is supereulerian.
基金Supported by National Natural Science Foundation of China(Grant No.11551002)Natural Science Foundation of Qinghai Province(Grant No.2019-ZJ-7093)。
文摘A strong product graph is denoted by G_(1)■G_(2),where G_(1) and G_(2) are called its factor graphs.This paper gives the range of the minimum strong radius of the strong product graph.And using the relationship between the cartesian product graph G_(1)■G_(2) and the strong product graph G_(1)■G_(2),another different upper bound of the minimum strong radius of the strong product graph is given.
基金the Scientific Technology Development Project of Heilongjiang(Grant No.WH05A01 and GB05A103)Scientific Technology Development Project of Harbin
文摘Based on the key function of version management in PDM system, this paper discusses the function and the realization of version management and the transitions of version states with a workflow. A directed aeyclic graph is used to describe a version model. Three storage modes of the directed acyelic graph version model in the database, the bumping block and the PDM working memory are presented and the conversion principle of these three modes is given. The study indicates that building a dynamic product structure configuration model based on versions is the key to resolve the problem. Thus a version model of single product object is built. Then the version management model in product structure configuration is built and the application of version management of PDM syster is presented as a case.
基金Supported by NSFC(Grant No.10771225)Fundamental Research Funds for the Central University
文摘In this paper, the cycle structures for directed graphs on surfaces are studied. If G is a strongly connected graph, C is a ∏-contractible directed cycle of G, then both of Int（C,∏） and Ext（C,∏） are strongly connected graph; the dimension of cycles space of G is identified. If G is a strongly connected graph, then the structure of MCB in G is unique. Let G be a strongly connected graph, if G has been embedded in orientable surface Sg with fw（G） ≥ 2（fw（G） is the face-width of G）, then any cycle base of G must contain at least 2g noncontractible directed cycles; if G has been embedded in non-orientable surface Ng, then any cycle base of G must contain at least g noncontractible directed cycles.
