共查询到20条相似文献,搜索用时 12 毫秒
1.
C. Balbuena 《Discrete Applied Mathematics》2007,155(18):2444-2455
The product graph Gm*Gp of two given graphs Gm and Gp was defined by Bermond et al. [Large graphs with given degree and diameter II, J. Combin. Theory Ser. B 36 (1984) 32-48]. For this kind of graphs we provide bounds for two connectivity parameters (λ and λ′, edge-connectivity and restricted edge-connectivity, respectively), and state sufficient conditions to guarantee optimal values of these parameters. Moreover, we compare our results with other previous related ones for permutation graphs and cartesian product graphs, obtaining several extensions and improvements. In this regard, for any two connected graphs Gm, Gp of minimum degrees δ(Gm), δ(Gp), respectively, we show that λ(Gm*Gp) is lower bounded by both δ(Gm)+λ(Gp) and δ(Gp)+λ(Gm), an improvement of what is known for the edge-connectivity of Gm×Gp. 相似文献
2.
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. 相似文献
3.
4.
《Discrete Mathematics》2023,346(1):113178
If each minimal dominating set in a graph is a minimum dominating set, then the graph is called well-dominated. Since the seminal paper on well-dominated graphs appeared in 1988, the structure of well-dominated graphs from several restricted classes has been studied. In this paper we give a complete characterization of nontrivial direct products that are well-dominated. We prove that if a strong product is well-dominated, then both of its factors are well-dominated. When one of the factors of a strong product is a complete graph, the other factor being well-dominated is also a sufficient condition for the product to be well-dominated. Our main result gives a complete characterization of well-dominated Cartesian products in which at least one of the factors is a complete graph. In addition, we conjecture that this result is actually a complete characterization of the class of nontrivial, well-dominated Cartesian products. 相似文献
5.
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 相似文献
6.
Yongxi Cheng 《Discrete Mathematics》2008,308(24):6441-6448
An antimagic labeling of a finite undirected simple graph with m edges and n vertices is a bijection from the set of edges to the integers 1,…,m such that all n-vertex sums are pairwise distinct, where a vertex sum is the sum of labels of all edges incident with the same vertex. A graph is called antimagic if it has an antimagic labeling. In 1990, Hartsfield and Ringel [N. Hartsfield, G. Ringel, Pearls in Graph Theory, Academic Press, INC., Boston, 1990, pp. 108-109, Revised version, 1994] conjectured that every simple connected graph, except K2, is antimagic. In this article, we prove that a new class of Cartesian product graphs are antimagic. In particular, by combining this result and the antimagicness result on toroidal grids (Cartesian products of two cycles) in [Tao-Ming Wang, Toroidal grids are anti-magic, in: Proc. 11th Annual International Computing and Combinatorics Conference COCOON’2005, in: LNCS, vol. 3595, Springer, 2005, pp. 671-679], all Cartesian products of two or more regular graphs of positive degree can be proved to be antimagic. 相似文献
7.
Ismael G. Yero 《Applied mathematics and computation》2010,217(7):3571-3574
Let G = (V, E) be a connected graph. The distance between two vertices u, v ∈ V, denoted by d(u, v), is the length of a shortest u − v path in G. The distance between a vertex v ∈ V and a subset P ⊂ V is defined as , and it is denoted by d(v, P). An ordered partition {P1, P2, … , Pt} of vertices of a graph G, is a resolving partition of G, if all the distance vectors (d(v, P1), d(v, P2), … , d(v, Pt)) are different. The partition dimension of G, denoted by pd(G), is the minimum number of sets in any resolving partition of G. In this article we study the partition dimension of Cartesian product graphs. More precisely, we show that for all pairs of connected graphs G, H, pd(G × H) ? pd(G) + pd(H) and pd(G × H) ? pd(G) + dim(H), where dim(H) denotes the metric dimension of H. Consequently, we show that pd(G × H) ? dim(G) + dim(H) + 1. 相似文献
8.
L. Barrière 《Discrete Mathematics》2009,309(12):3871-871
A generalization of both the hierarchical product and the Cartesian product of graphs is introduced and some of its properties are studied. We call it the generalized hierarchical product. In fact, the obtained graphs turn out to be subgraphs of the Cartesian product of the corresponding factors. Thus, some well-known properties of this product, such as a good connectivity, reduced mean distance, radius and diameter, simple routing algorithms and some optimal communication protocols, are inherited by the generalized hierarchical product. Besides some of these properties, in this paper we study the spectrum, the existence of Hamiltonian cycles, the chromatic number and index, and the connectivity of the generalized hierarchical product. 相似文献
9.
The Cartesian product of a closed, orientable prime geometric 3-manifold and a closed orientable surface is unique except for the case of the Cartesian product of a special class of Seifert manifolds and a torus. The same type of uniqueness holds for stabilization of 3-manifolds by an n-dimensional torus. Cartesian squares of Seifert fibered 3-manifolds are completely classified. 相似文献
10.
Boštjan Brešar 《Discrete Mathematics》2008,308(23):5555-5561
A set S of vertices of a graph G is a geodetic set if every vertex of G lies in at least one interval between the vertices of S. The size of a minimum geodetic set in G is the geodetic number of G. Upper bounds for the geodetic number of Cartesian product graphs are proved and for several classes exact values are obtained. It is proved that many metrically defined sets in Cartesian products have product structure and that the contour set of a Cartesian product is geodetic if and only if their projections are geodetic sets in factors. 相似文献
11.
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. 相似文献
12.
We show that every nontrivial finite or infinite connected directed graph with loops and at least one vertex without a loop is uniquely representable as a Cartesian or weak Cartesian product of prime graphs. For finite graphs the factorization can be computed in linear time and space. 相似文献
13.
Zoltán Szigeti 《Discrete Applied Mathematics》2008,156(7):1011-1018
Let G=(V+s,E) be a 2-edge-connected graph with a designated vertex s. A pair of edges rs,st is called admissible if splitting off these edges (replacing rs and st by rt) preserves the local edge-connectivity (the maximum number of pairwise edge disjoint paths) between each pair of vertices in V. The operation splitting off is very useful in graph theory, it is especially powerful in the solution of edge-connectivity augmentation problems as it was shown by Frank [Augmenting graphs to meet edge-connectivity requirements, SIAM J. Discrete Math. 5(1) (1992) 22-53]. Mader [A reduction method for edge-connectivity in graphs, Ann. Discrete Math. 3 (1978) 145-164] proved that if d(s)≠3 then there exists an admissible pair incident to s. We generalize this result by showing that if d(s)?4 then there exists an edge incident to s that belongs to at least ⌊d(s)/3⌋ admissible pairs. An infinite family of graphs shows that this bound is best possible. We also refine a result of Frank [On a theorem of Mader, Discrete Math. 101 (1992) 49-57] by describing the structure of the graph if an edge incident to s belongs to no admissible pairs. This provides a new proof for Mader's theorem. 相似文献
14.
Byeong Moon Kim 《Linear algebra and its applications》2008,429(4):841-848
We show that mn-1 is an upper bound of the exponent of the Cartesian product D×E of two digraphs D and E on m,n vertices, respectively and we prove our upper bound is extremal when (m,n)=1. We also find all D and E when the exponent of D×E is mn-1. In addition, when m=n, we prove that the extremal upper bound of exp(D×E) is n2-n+1 and only the Cartesian product, Zn×Wn, of the directed cycle and Wielandt digraph has exponent equals to this bound. 相似文献
15.
Upper bound of the third edge-connectivity of graphs 总被引:6,自引:0,他引:6
WANG Yingqian & LI Qiao Department of Mathematics Zhejiang Normal University Jinhua China Department of Applied Mathematics Shanghai Jiaotong University Shanghai China 《中国科学A辑(英文版)》2005,48(3):360-371
Let G be a simple connected graph of order n≥6. The third edge-connectivity of G is defined as the minimum cardinality over all the sets of edges, if any, whose deletion disconnects G and every component of the resulting graph has at least 3 vertices. In this paper, we first characterize those graphs whose third-edge connectivity is well defined, then establish the tight upper bound for the third edge-connectivity. 相似文献
16.
Bing Wang 《Discrete Mathematics》2009,309(13):4555-4563
A cyclic edge-cut of a graph G is an edge set, the removal of which separates two cycles. If G has a cyclic edge-cut, then it is said to be cyclically separable. For a cyclically separable graph G, the cyclic edge-connectivity cλ(G) is the cardinality of a minimum cyclic edge-cut of G. In this paper, we first prove that for any cyclically separable graph G, , where ω(X) is the number of edges with one end in X and the other end in V(G)?X. A cyclically separable graph G with cλ(G)=ζ(G) is said to be cyclically optimal. The main results in this paper are: any connected k-regular vertex-transitive graph with k≥4 and girth at least 5 is cyclically optimal; any connected edge-transitive graph with minimum degree at least 4 and order at least 6 is cyclically optimal. 相似文献
17.
WANG Yingqian Department of Mathematics Zhejiang Normal University Jinhua China 《中国科学A辑(英文版)》2006,49(6):791-799
The third edge-connectivity λ3(G) of a graph G is defined as the minimum cardinality over all sets of edges, if any, whose deletion disconnects G and each component of the resulting graph has at least 3 vertices. An upper bound has been established for λ3(G) whenever λ3(G) is well-defined. This paper first introduces two combinatorial optimization concepts, that is, maximality and superiority, of λ3(G), and then proves the Ore type sufficient conditions for G to be maximally and super third edge-connected. These concepts and results are useful in network reliability analysis. 相似文献
18.
19.
20.