Cycle multiplicity of a graph G is the maximum number of edge disjoint cycles in G. In this paper, we determine the cycle multiplicity of and then obtain the formula of cycle multiplicity of total graph of complete bi...Cycle multiplicity of a graph G is the maximum number of edge disjoint cycles in G. In this paper, we determine the cycle multiplicity of and then obtain the formula of cycle multiplicity of total graph of complete bipartite graph, this generalizes the result for, which is given by M.M. Akbar Ali in [1].展开更多
Let G be a simple graph. A total coloring f of G is called an E-total coloring if no two adjacent vertices of G receive the same color, and no edge of G receives the same color as one of its endpoints....Let G be a simple graph. A total coloring f of G is called an E-total coloring if no two adjacent vertices of G receive the same color, and no edge of G receives the same color as one of its endpoints. For an E-total coloring f of a graph G and any vertex x of G, let C（x） denote the set of colors of vertex x and of the edges incident with x, we call C（x） the color set of x. If C（u） ≠ C（v） for any two different vertices u and v of V （G）, then we say that f is a vertex-distinguishing E-total coloring of G or a VDET coloring of G for short. The minimum number of colors required for a VDET coloring of G is denoted by Хvt^e（G） and is called the VDE T chromatic number of G. The VDET coloring of complete bipartite graph K7,n （7 ≤ n ≤ 95） is discussed in this paper and the VDET chromatic number of K7,n （7 ≤ n ≤ 95） has been obtained.展开更多
A signed(res. signed total) Roman dominating function, SRDF(res.STRDF) for short, of a graph G =(V, E) is a function f : V → {-1, 1, 2} satisfying the conditions that(i)∑v∈N[v]f(v) ≥ 1(res.∑v∈N(v)f(v) ≥ 1) for ...A signed(res. signed total) Roman dominating function, SRDF(res.STRDF) for short, of a graph G =(V, E) is a function f : V → {-1, 1, 2} satisfying the conditions that(i)∑v∈N[v]f(v) ≥ 1(res.∑v∈N(v)f(v) ≥ 1) for any v ∈ V, where N [v] is the closed neighborhood and N(v) is the neighborhood of v, and(ii) every vertex v for which f(v) =-1 is adjacent to a vertex u for which f(u) = 2. The weight of a SRDF(res. STRDF) is the sum of its function values over all vertices.The signed(res. signed total) Roman domination number of G is the minimum weight among all signed(res. signed total) Roman dominating functions of G. In this paper,we compute the exact values of the signed(res. signed total) Roman domination numbers of complete bipartite graphs and wheels.展开更多
Let G be a simple graph. An IE-total coloring f of G is a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color. For each vertex x of G, let C(x) be the set of colors of verte...Let G be a simple graph. An IE-total coloring f of G is a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color. For each vertex x of G, let C(x) be the set of colors of vertex x and edges incident to x under f. For an IE-total coloring f of G using k colors, if C(u) ≠ C(v) for any two different vertices u and v of G, then f is called a k-vertex-distinguishing IE-total-coloring of G or a k-VDIET coloring of G for short. The minimum number of colors required for a VDIET coloring of G is denoted by χ_(vt)^(ie) (G) and is called vertex-distinguishing IE-total chromatic number or the VDIET chromatic number of G for short. The VDIET colorings of complete bipartite graphs K_(8,n)are discussed in this paper. Particularly, the VDIET chromatic number of K_(8,n) are obtained.展开更多
Let be a family of subgraphs of a graph G. An L-decomposition of G is an edge-disjoint decomposition of G into positive integer copies of H<sub>i</sub>, where . Let C<sub>k</sub>, P<sub>k...Let be a family of subgraphs of a graph G. An L-decomposition of G is an edge-disjoint decomposition of G into positive integer copies of H<sub>i</sub>, where . Let C<sub>k</sub>, P<sub>k</sub> and S<sub>k</sub> denote a cycle, a path and a star with k edges, respectively. For an integer , we prove that a balanced complete bipartite multigraph has a -decomposition if and only if k is even, and .展开更多
LetλK_(m,n)be a complete bipartite multigraph with two partite sets having m and n vertices,respectively.A K_(p,q)-factorization ofλK_(m,n)is a set of K_(p,q)-factors ofλK_(m,n)which partition the set of edges ofλ...LetλK_(m,n)be a complete bipartite multigraph with two partite sets having m and n vertices,respectively.A K_(p,q)-factorization ofλK_(m,n)is a set of K_(p,q)-factors ofλK_(m,n)which partition the set of edges ofλK_(m,n).Whenλ=1,Martin,in[Complete bipartite factorizations by complete bipartite graphs,Discrete Math.,167/168(1997),461–480],gave simple necessary conditions for such a factorization to exist,and conjectured those conditions are always sufficient.In this paper,we will study the K_(p,q)-factorization ofλK_(m,n)for p=1,to show that the necessary conditions for such a factorization are always sufficient whenever related parameters are sufficiently large.展开更多
The pebbling number of a graph G,f(G),is the least n such that,no matter how n pebbles are placed on the vertices of G,we can move a pebble to any vertex by a sequence of moves,each move taking two pebbles off one ver...The pebbling number of a graph G,f(G),is the least n such that,no matter how n pebbles are placed on the vertices of G,we can move a pebble to any vertex by a sequence of moves,each move taking two pebbles off one vertex and placing one on an adjacent vertex.Graham conjectured that for any connected graphs G and H,f(G×H)≤f(G)f(H).We show that Graham's conjecture holds true of a complete bipartite graph by a graph with the two-pebbling property.As a corollary,Graham's conjecture holds when G and H are complete bipartite graphs.展开更多
Users are vulnerable to privacy risks when providing their location information to location-based services （LBS）. Existing work sacrifices the quality of LBS by degrading spatial and temporal accuracy for ensuring u...Users are vulnerable to privacy risks when providing their location information to location-based services （LBS）. Existing work sacrifices the quality of LBS by degrading spatial and temporal accuracy for ensuring user privacy. In this paper, we propose a novel approach, Complete Bipartite Anonymity （CBA）, aiming to achieve both user privacy and quality of service. The theoretical basis of CBA is that： if the bipartite graph of k nearby users＇ paths can be transformed into a complete bipartite graph, then these users achieve k-anonymity since the set of ＂end points connecting to a specific start point in a graph＂ is an equivalence class. To achieve CBA, we design a Collaborative Path Confusion （CPC） protocol which enables nearby nsers to discover and authenticate each other without knowing their real identities or accurate locations, predict tile encounter location using users＇ moving pattern information, and generate fake traces obfuscating the real ones. We evaluate CBA using a real-world dataset, and compare its privacy performance with existing path confusion approach. The results show that CBA enhances location privacy by increasing the chance for a user confusing his/her path with others by 4 to 16 times in low user density areas. We also demonstrate that CBA is secure under the trace identification attack.展开更多
In [1] the concepts of paths and cycles of a hypergraph were introduced. In this paper, we give the concepts for bipartite hypergraph and Hamiltonian paths and cycles of a hypergraph, and prove that the complete bipar...In [1] the concepts of paths and cycles of a hypergraph were introduced. In this paper, we give the concepts for bipartite hypergraph and Hamiltonian paths and cycles of a hypergraph, and prove that the complete bipartite 3-hypergraph with q vertices in earh part is Hamiltonian decomposable where q is a prime.展开更多
Let G = (V,E) be a simple graph without isolated vertices. For positive integer k, a 3-valued function f : V → {-1,0,1} is said to be a minus total k-subdominating function (MTkSF) if sum from (u∈N(v)) to f(u)≥1 fo...Let G = (V,E) be a simple graph without isolated vertices. For positive integer k, a 3-valued function f : V → {-1,0,1} is said to be a minus total k-subdominating function (MTkSF) if sum from (u∈N(v)) to f(u)≥1 for at least k vertices v in G, where N(v) is the open neighborhood of v. The minus total k-subdomination number γkt(G) equals the minimum weight of an MTkSF on G. In this paper, the values on the minus total k-subdomination number of some special graphs are investigated. Several lower bounds on γkt of general graphs and trees are obtained.展开更多
文摘Cycle multiplicity of a graph G is the maximum number of edge disjoint cycles in G. In this paper, we determine the cycle multiplicity of and then obtain the formula of cycle multiplicity of total graph of complete bipartite graph, this generalizes the result for, which is given by M.M. Akbar Ali in [1].
文摘Let G be a simple graph. A total coloring f of G is called an E-total coloring if no two adjacent vertices of G receive the same color, and no edge of G receives the same color as one of its endpoints. For an E-total coloring f of a graph G and any vertex x of G, let C（x） denote the set of colors of vertex x and of the edges incident with x, we call C（x） the color set of x. If C（u） ≠ C（v） for any two different vertices u and v of V （G）, then we say that f is a vertex-distinguishing E-total coloring of G or a VDET coloring of G for short. The minimum number of colors required for a VDET coloring of G is denoted by Хvt^e（G） and is called the VDE T chromatic number of G. The VDET coloring of complete bipartite graph K7,n （7 ≤ n ≤ 95） is discussed in this paper and the VDET chromatic number of K7,n （7 ≤ n ≤ 95） has been obtained.
基金The NSF(11271365)of Chinathe NSF(BK20151117)of Jiangsu Province
文摘A signed(res. signed total) Roman dominating function, SRDF(res.STRDF) for short, of a graph G =(V, E) is a function f : V → {-1, 1, 2} satisfying the conditions that(i)∑v∈N[v]f(v) ≥ 1(res.∑v∈N(v)f(v) ≥ 1) for any v ∈ V, where N [v] is the closed neighborhood and N(v) is the neighborhood of v, and(ii) every vertex v for which f(v) =-1 is adjacent to a vertex u for which f(u) = 2. The weight of a SRDF(res. STRDF) is the sum of its function values over all vertices.The signed(res. signed total) Roman domination number of G is the minimum weight among all signed(res. signed total) Roman dominating functions of G. In this paper,we compute the exact values of the signed(res. signed total) Roman domination numbers of complete bipartite graphs and wheels.
基金Supported by the National Natural Science Foundation of China（61163037, 61163054, 11261046, 61363060）
文摘Let G be a simple graph. An IE-total coloring f of G is a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color. For each vertex x of G, let C(x) be the set of colors of vertex x and edges incident to x under f. For an IE-total coloring f of G using k colors, if C(u) ≠ C(v) for any two different vertices u and v of G, then f is called a k-vertex-distinguishing IE-total-coloring of G or a k-VDIET coloring of G for short. The minimum number of colors required for a VDIET coloring of G is denoted by χ_(vt)^(ie) (G) and is called vertex-distinguishing IE-total chromatic number or the VDIET chromatic number of G for short. The VDIET colorings of complete bipartite graphs K_(8,n)are discussed in this paper. Particularly, the VDIET chromatic number of K_(8,n) are obtained.
文摘Let be a family of subgraphs of a graph G. An L-decomposition of G is an edge-disjoint decomposition of G into positive integer copies of H<sub>i</sub>, where . Let C<sub>k</sub>, P<sub>k</sub> and S<sub>k</sub> denote a cycle, a path and a star with k edges, respectively. For an integer , we prove that a balanced complete bipartite multigraph has a -decomposition if and only if k is even, and .
基金supported by the National Natural Science Foundation of China (Grant No.K110703711)。
文摘LetλK_(m,n)be a complete bipartite multigraph with two partite sets having m and n vertices,respectively.A K_(p,q)-factorization ofλK_(m,n)is a set of K_(p,q)-factors ofλK_(m,n)which partition the set of edges ofλK_(m,n).Whenλ=1,Martin,in[Complete bipartite factorizations by complete bipartite graphs,Discrete Math.,167/168(1997),461–480],gave simple necessary conditions for such a factorization to exist,and conjectured those conditions are always sufficient.In this paper,we will study the K_(p,q)-factorization ofλK_(m,n)for p=1,to show that the necessary conditions for such a factorization are always sufficient whenever related parameters are sufficiently large.
基金This work was supported by the National Natural Science Foundation of China (Grant Nos. 49873002, 10001005).
文摘The pebbling number of a graph G,f(G),is the least n such that,no matter how n pebbles are placed on the vertices of G,we can move a pebble to any vertex by a sequence of moves,each move taking two pebbles off one vertex and placing one on an adjacent vertex.Graham conjectured that for any connected graphs G and H,f(G×H)≤f(G)f(H).We show that Graham's conjecture holds true of a complete bipartite graph by a graph with the two-pebbling property.As a corollary,Graham's conjecture holds when G and H are complete bipartite graphs.
基金supported by the National Natural Science Foundation of China under Grant Nos.61373011,91318301,and 61321491
文摘Users are vulnerable to privacy risks when providing their location information to location-based services （LBS）. Existing work sacrifices the quality of LBS by degrading spatial and temporal accuracy for ensuring user privacy. In this paper, we propose a novel approach, Complete Bipartite Anonymity （CBA）, aiming to achieve both user privacy and quality of service. The theoretical basis of CBA is that： if the bipartite graph of k nearby users＇ paths can be transformed into a complete bipartite graph, then these users achieve k-anonymity since the set of ＂end points connecting to a specific start point in a graph＂ is an equivalence class. To achieve CBA, we design a Collaborative Path Confusion （CPC） protocol which enables nearby nsers to discover and authenticate each other without knowing their real identities or accurate locations, predict tile encounter location using users＇ moving pattern information, and generate fake traces obfuscating the real ones. We evaluate CBA using a real-world dataset, and compare its privacy performance with existing path confusion approach. The results show that CBA enhances location privacy by increasing the chance for a user confusing his/her path with others by 4 to 16 times in low user density areas. We also demonstrate that CBA is secure under the trace identification attack.
基金the National Natural Science Foundation of China (No.19831080).
文摘In [1] the concepts of paths and cycles of a hypergraph were introduced. In this paper, we give the concepts for bipartite hypergraph and Hamiltonian paths and cycles of a hypergraph, and prove that the complete bipartite 3-hypergraph with q vertices in earh part is Hamiltonian decomposable where q is a prime.
基金supported by the National Natural Science Foundation of China (Grant No.10571117)the Development Foundation of Shanghai Municipal Education Commission (Grant No.05AZ04)
文摘Let G = (V,E) be a simple graph without isolated vertices. For positive integer k, a 3-valued function f : V → {-1,0,1} is said to be a minus total k-subdominating function (MTkSF) if sum from (u∈N(v)) to f(u)≥1 for at least k vertices v in G, where N(v) is the open neighborhood of v. The minus total k-subdomination number γkt(G) equals the minimum weight of an MTkSF on G. In this paper, the values on the minus total k-subdomination number of some special graphs are investigated. Several lower bounds on γkt of general graphs and trees are obtained.
