We investigate the dominating-c-color number,, of a graph G. That is the maximum number of color classes that are also dominating when G is colored using colors. We show that where is the join of G and . This result a...We investigate the dominating-c-color number,, of a graph G. That is the maximum number of color classes that are also dominating when G is colored using colors. We show that where is the join of G and . This result allows us to construct classes of graphs such that and thus provide some information regarding two questions raised in [1] and [2].展开更多
Let G=(V,E) be a simple graph. A subset D of V is called a dominating set of G if for every vertex x∈V-D,x is adjacent to at least one vertex of D . Let γ(G) and γ c(G) denote the ...Let G=(V,E) be a simple graph. A subset D of V is called a dominating set of G if for every vertex x∈V-D,x is adjacent to at least one vertex of D . Let γ(G) and γ c(G) denote the domination and connected domination number of G , respectively. In 1965,Vizing conjectured that if G×H is the Cartesian product of G and H , thenγ(G×H)≥γ(G)·γ(H).In this paper, it is showed that the conjecture holds if γ(H) ≠ γ c(H) .And for paths P m and P n , a lower bound and an upper bound for γ(P m×P n) are obtained.展开更多
Let <em>G</em>(<em>V</em>, <em>E</em>) be a finite connected simple graph with vertex set <em>V</em>(<em>G</em>). A function is a signed dominating function ...Let <em>G</em>(<em>V</em>, <em>E</em>) be a finite connected simple graph with vertex set <em>V</em>(<em>G</em>). A function is a signed dominating function <em>f </em>: <em style="white-space:normal;">V</em><span style="white-space:normal;">(</span><em style="white-space:normal;">G</em><span style="white-space:normal;">)</span><span style="white-space:nowrap;">→{<span style="white-space:nowrap;"><span style="white-space:nowrap;">−</span></span>1,1}</span> if for every vertex <em>v</em> <span style="white-space:nowrap;">∈</span> <em>V</em>(<em>G</em>), the sum of closed neighborhood weights of <em>v</em> is greater or equal to 1. The signed domination number <em>γ</em><sub>s</sub>(<em>G</em>) of <em>G</em> is the minimum weight of a signed dominating function on <em>G</em>. In this paper, we calculate the signed domination numbers of the Cartesian product of two paths <em>P</em><sub><em>m</em></sub> and <em>P</em><sub><em>n</em></sub> for <em>m</em> = 6, 7 and arbitrary <em>n</em>.展开更多
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.展开更多
A set D of vertices of a graph G = （V, E） is called a dominating set if every vertex of V not in D is adjacent to a vertex of D. In 1996, Reed proved that every graph of order n with minimum degree at least 3 has a ...A set D of vertices of a graph G = （V, E） is called a dominating set if every vertex of V not in D is adjacent to a vertex of D. In 1996, Reed proved that every graph of order n with minimum degree at least 3 has a dominating set of cardinality at most 3n/8. In this paper we generalize Reed＇s result. We show that every graph G of order n with minimum degree at least 2 has a dominating set of cardinality at most （3n ＋IV21）/8, where V2 denotes the set of vertices of degree 2 in G. As an application of the above result, we show that for k ≥ 1, the k-restricted domination number rk （G, γ） ≤ （3n＋5k）/8 for all graphs of order n with minimum degree at least 3.展开更多
A graph G is said to have a perfect dominating set S if S is a set of vertices of G and for each vertex v of G, either v is in S and v is adjacent to no other vertex in S, or v is not in S but is adjacent to precisely...A graph G is said to have a perfect dominating set S if S is a set of vertices of G and for each vertex v of G, either v is in S and v is adjacent to no other vertex in S, or v is not in S but is adjacent to precisely one vertex of S. A graph G may have none, one or more than one perfect dominating sets. The problem of determining if a graph has a perfect dominating set is NP-complete. The problem of calculating the probability of an arbitrary graph having a perfect dominating set seems also difficult. In 1994 Yue [1] conjectured that almost all graphs do not have a perfect dominating set. In this paper, by introducing multiple interrelated generating functions and using combinatorial computation techniques we calculated the number of perfect dominating sets among all trees (rooted and unrooted) of order n for each n up to 500. Then we calculated the average number of perfect dominating sets per tree (rooted and unrooted) of order n for each n up to 500. Our computational results show that this average number is approaching zero as n goes to infinity thus suggesting that Yue’s conjecture is true for trees (rooted and unrooted).展开更多
文摘We investigate the dominating-c-color number,, of a graph G. That is the maximum number of color classes that are also dominating when G is colored using colors. We show that where is the join of G and . This result allows us to construct classes of graphs such that and thus provide some information regarding two questions raised in [1] and [2].
文摘Let G=(V,E) be a simple graph. A subset D of V is called a dominating set of G if for every vertex x∈V-D,x is adjacent to at least one vertex of D . Let γ(G) and γ c(G) denote the domination and connected domination number of G , respectively. In 1965,Vizing conjectured that if G×H is the Cartesian product of G and H , thenγ(G×H)≥γ(G)·γ(H).In this paper, it is showed that the conjecture holds if γ(H) ≠ γ c(H) .And for paths P m and P n , a lower bound and an upper bound for γ(P m×P n) are obtained.
文摘Let <em>G</em>(<em>V</em>, <em>E</em>) be a finite connected simple graph with vertex set <em>V</em>(<em>G</em>). A function is a signed dominating function <em>f </em>: <em style="white-space:normal;">V</em><span style="white-space:normal;">(</span><em style="white-space:normal;">G</em><span style="white-space:normal;">)</span><span style="white-space:nowrap;">→{<span style="white-space:nowrap;"><span style="white-space:nowrap;">−</span></span>1,1}</span> if for every vertex <em>v</em> <span style="white-space:nowrap;">∈</span> <em>V</em>(<em>G</em>), the sum of closed neighborhood weights of <em>v</em> is greater or equal to 1. The signed domination number <em>γ</em><sub>s</sub>(<em>G</em>) of <em>G</em> is the minimum weight of a signed dominating function on <em>G</em>. In this paper, we calculate the signed domination numbers of the Cartesian product of two paths <em>P</em><sub><em>m</em></sub> and <em>P</em><sub><em>n</em></sub> for <em>m</em> = 6, 7 and arbitrary <em>n</em>.
文摘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.
基金supported by Korea Research Foundation Grant (KRF-2002-015-cp0050)the National Natural Science Foundation of China (Grant Nos. 60773078, 10571117)+3 种基金the ShuGuang Plan of Shanghai Education Development Foundation (Grant No. 06SG42)M. A. Henning is supported in part by the South African National Research Foundationthe University of KwaZulu-Natalsupported by Shanghai Leading Academic Discipline Project (No. $30104)
文摘A set D of vertices of a graph G = （V, E） is called a dominating set if every vertex of V not in D is adjacent to a vertex of D. In 1996, Reed proved that every graph of order n with minimum degree at least 3 has a dominating set of cardinality at most 3n/8. In this paper we generalize Reed＇s result. We show that every graph G of order n with minimum degree at least 2 has a dominating set of cardinality at most （3n ＋IV21）/8, where V2 denotes the set of vertices of degree 2 in G. As an application of the above result, we show that for k ≥ 1, the k-restricted domination number rk （G, γ） ≤ （3n＋5k）/8 for all graphs of order n with minimum degree at least 3.
文摘A graph G is said to have a perfect dominating set S if S is a set of vertices of G and for each vertex v of G, either v is in S and v is adjacent to no other vertex in S, or v is not in S but is adjacent to precisely one vertex of S. A graph G may have none, one or more than one perfect dominating sets. The problem of determining if a graph has a perfect dominating set is NP-complete. The problem of calculating the probability of an arbitrary graph having a perfect dominating set seems also difficult. In 1994 Yue [1] conjectured that almost all graphs do not have a perfect dominating set. In this paper, by introducing multiple interrelated generating functions and using combinatorial computation techniques we calculated the number of perfect dominating sets among all trees (rooted and unrooted) of order n for each n up to 500. Then we calculated the average number of perfect dominating sets per tree (rooted and unrooted) of order n for each n up to 500. Our computational results show that this average number is approaching zero as n goes to infinity thus suggesting that Yue’s conjecture is true for trees (rooted and unrooted).
