共查询到20条相似文献,搜索用时 15 毫秒
1.
2.
3.
Given a graph G, a proper labelingf of G is a one-to-one function from V(G) onto {1,2,…,|V(G)|}. For a proper labeling f of G, the profile widthwf(v) of a vertex v is the minimum value of f(v)−f(x), where x belongs to the closed neighborhood of v. The profile of a proper labelingfofG, denoted by Pf(G), is the sum of all the wf(v), where v∈V(G). The profile ofG is the minimum value of Pf(G), where f runs over all proper labeling of G. In this paper, we show that if the vertices of a graph G can be ordered to satisfy a special neighborhood property, then so can the graph G×Qn. This can be used to determine the profile of Qn and Km×Qn. 相似文献
4.
Use vi,κi,λi,δi to denote order, connectivity, edge-connectivity and minimum degree of a graph Gi for i=1,2, respectively. For the connectivity and the edge-connectivity of the Cartesian product graph, up to now, the best results are κ(G1×G2)?κ1+κ2 and λ(G1×G2)?λ1+λ2. This paper improves these results by proving that κ(G1×G2)?min{κ1+δ2,κ2+δ1} and λ(G1×G2)=min{δ1+δ2,λ1v2,λ2v1} if G1 and G2 are connected undirected graphs; κ(G1×G2)?min{κ1+δ2,κ2+δ1,2κ1+κ2,2κ2+κ1} if G1 and G2 are strongly connected digraphs. These results are also generalized to the Cartesian products of connected graphs and n strongly connected digraphs, respectively. 相似文献
5.
The circular chromatic index of a graph G, written , is the minimum r permitting a function such that whenever e and are incident. Let □ , where □ denotes Cartesian product and H is an ‐regular graph of odd order, with (thus, G is s‐regular). We prove that , where is the minimum, over all bases of the cycle space of H, of the maximum length of a cycle in the basis. When and m is large, the lower bound is sharp. In particular, if , then □ , independent of m. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 7–18, 2008 相似文献
6.
Upper and lower bounds are given for the genus, γ(G1 × G2), of the Cartesian product of arbitrary graphs G1 and G2, in terms of the genera γ(G1) and γ(G2). These bounds are then used to obtain asymptotic results for the cases in which G1 and G2 are both regular complete k-partite graphs. 相似文献
7.
8.
Xuding Zhu 《Journal of Graph Theory》2008,59(4):261-278
This article proves the following result: Let G and G′ be graphs of orders n and n′, respectively. Let G* be obtained from G by adding to each vertex a set of n′ degree 1 neighbors. If G* has game coloring number m and G′ has acyclic chromatic number k, then the Cartesian product G□G′ has game chromatic number at most k(k + m ? 1). As a consequence, the Cartesian product of two forests has game chromatic number at most 10, and the Cartesian product of two planar graphs has game chromatic number at most 105. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 261–278, 2008 相似文献
9.
Janja Jerebic 《Discrete Mathematics》2010,310(12):1715-1720
A labeling of a graph G is distinguishing if it is only preserved by the trivial automorphism of G. The distinguishing chromatic number of G is the smallest integer k such that G has a distinguishing labeling that is at the same time a proper vertex coloring. The distinguishing chromatic number of the Cartesian product is determined for all k and n. In most of the cases it is equal to the chromatic number, thus answering a question of Choi, Hartke and Kaul whether there are some other graphs for which this equality holds. 相似文献
10.
Jun-Yang Zhang 《Discrete Mathematics》2012,312(2):258-264
11.
Let αk(G) denote the maximum number of vertices in a k-colorable subgraph of G. Set αk(G)=αk(G)?α(k?1)(G). The sequence a1(G), a2(G),… is called the chromatic difference sequence of the graph G. We present necessary and sufficient conditions for a sequence to be the chromatic difference sequence of some 4-colorable graph. 相似文献
12.
Junior Michel José M. Rodríguez José M. Sigarreta María Villeta 《Proceedings Mathematical Sciences》2010,120(5):593-609
If X is a geodesic metric space and x
1, x
2, x
3 ∈ X, a geodesic triangle T = {x
1, x
2, x
3} is the union of the three geodesics [x
1
x
2], [x
2
x
3] and [x
3
x
1] in X. The space X is δ-hyperbolic (in the Gromov sense) if any side of T is contained in a δ-neighborhood of the union of the two other sides, for every geodesic triangle T in X. If X is hyperbolic, we denote by δ(X) the sharp hyperbolicity constant of X, i.e. δ(X) = inf{δ ≥ 0: X is δ-hyperbolic}. In this paper we characterize the product graphs G
1 × G
2 which are hyperbolic, in terms of G
1 and G
2: the product graph G
1 × G
2 is hyperbolic if and only if G
1 is hyperbolic and G
2 is bounded or G
2 is hyperbolic and G
1 is bounded. We also prove some sharp relations between the hyperbolicity constant of G
1 × G
2, δ(G
1), δ(G
2) and the diameters of G
1 and G
2 (and we find families of graphs for which the inequalities are attained). Furthermore, we obtain the precise value of the
hyperbolicity constant for many product graphs. 相似文献
13.
Changping Wang 《Discrete Applied Mathematics》2007,155(11):1497-1505
Let G be a graph with vertex set V(G) and edge set E(G). A function f:E(G)→{-1,1} is said to be a signed star dominating function of G if for every v∈V(G), where EG(v)={uv∈E(G)|u∈V(G)}. The minimum of the values of , taken over all signed star dominating functions f on G, is called the signed star domination number of G and is denoted by γSS(G). In this paper, a sharp upper bound of γSS(G×H) is presented. 相似文献
14.
Let αk(G) denote the maximum number of vertices in a k-colorable subgraph of G. Set αk=αk(G)-α(k-1)(G). The sequence a1(G),a2(G),… is called the chromatic difference sequence (cds) of G. We call a graph G critical if no proper subgraph of G has the same cds as G. We prove that (with a single exception) if there exists a graph G having cds (G)=〈a1,a2,a3〉 (a3>) and if a1?a2+a3, then there exists a connected critical graph H with cds(H)= 〈a1, a2,a2〉. 相似文献
15.
Gábor Mészáros 《Periodica Mathematica Hungarica》2016,72(2):130-138
We study linkedness of the Cartesian product of graphs and prove that the product of an a-linked and a b-linked graph is \((a+b-1)\)-linked if the graphs are sufficiently large. Further bounds in terms of connectivity are shown. We determine linkedness of products of paths and products of cycles. 相似文献
16.
The generalized k-connectivity κ k (G) of a graph G was introduced by Chartrand et al. in 1984. As a natural counterpart of this concept, Li et al. in 2011 introduced the concept of generalized k-edge-connectivity which is defined as λ k (G) = min{λ(S): S ? V (G) and |S| = k}, where λ(S) denotes the maximum number l of pairwise edge-disjoint trees T 1, T 2, …, T l in G such that S ? V (T i ) for 1 ? i ? l. In this paper we prove that for any two connected graphs G and H we have λ 3(G □ H) ? λ 3(G) + λ 3(H), where G □ H is the Cartesian product of G and H. Moreover, the bound is sharp. We also obtain the precise values for the generalized 3-edge-connectivity of the Cartesian product of some special graph classes. 相似文献
17.
18.
《Discrete Mathematics》2023,346(1):113162
The graph coloring game is a two-player game in which the two players properly color an uncolored vertex of G alternately. The first player wins the game if all vertices of G are colored, and the second wins otherwise. The game chromatic number of a graph G is the minimum integer k such that the first player has a winning strategy for the graph coloring game on G with k colors. There is a lot of literature on the game chromatic number of graph products, e.g., the Cartesian product and the lexicographic product. In this paper, we investigate the game chromatic number of the strong product of graphs, which is one of major graph products. In particular, we completely determine the game chromatic number of the strong product of a double star and a complete graph. Moreover, we estimate the game chromatic number of some King's graphs, which are the strong products of two paths. 相似文献
19.