首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 31 毫秒
1.
A graph G is called the 2-amalgamation of subgraphs G1 and G2 if G = G1G2 and G1G2 = {x, y}, 2 distinct points. in this case we write G = G1{x, y} G2. in this paper we show that the orientable genus, γ(G), satisfies the inequalities γ(G1) + γ(G2) ? 1 ≤ γ(G1{x, y} G2) ≤ γ(G1) + γ(G2) + 1 and that this is the best possible result, i. e., the resulting three values for γ(G1{x, y} G2) which are possible can actually be realized by appropriate choices for G1 and G2.  相似文献   

2.
Let G be a locally compact group and LUC(G) the C*-algebra of the bounded left uniformly continuous functions on G. The spectrum G LUC of LUC(G) is the universal semigroup compactification of G with respect to the joint continuity property: the multiplication on G×G LUC is jointly continuous. The paper studies the joint weak* continuity of multiplication on LUC(G)* and, in particular, the question how the joint continuity property of G LUC can be related to a property concerning the whole algebra LUC(G)*. The group G is naturally replaced by the measure algebra M(G), and LUC(G)* can be identified with M(G LUC), the space of regular Borel measures on G LUC. It is shown that the joint weak* continuity can fail even on bounded sets of M(G)×M(G LUC), but, on the other hand, the multiplication on M(G)×M(G LUC) is positive continuous in the sense of Jewett.  相似文献   

3.
The above authors [2] and S. Stahl [3] have shown that if a graphG is the 2-amalgamation of subgraphsG 1 andG 2 (namely ifG=G 1G 2 andG 1G 2={x, y}, two distinct points) then the orientable genus ofG,γ(G), is given byγ(G)=γ(G 1)+γ(G 2)+ε, whereε=0,1 or −1. In this paper we sharpen that result by giving a means by whichε may be computed exactly. This result is then used to give two irreducible graphs for each orientable surface.  相似文献   

4.
Let G be a connected graph and η(G)=Sz(G)−W(G), where W(G) and Sz(G) are the Wiener and Szeged indices of G, respectively. A well-known result of Klav?ar, Rajapakse, and Gutman states that η(G)≥0, and by a result of Dobrynin and Gutman η(G)=0 if and only if each block of G is complete. In this paper, a path-edge matrix for the graph G is presented by which it is possible to classify the graphs in which η(G)=2. It is also proved that there is no graph G with the property that η(G)=1 or η(G)=3. Finally, it is proved that, for a given positive integer k,k≠1,3, there exists a graph G with η(G)=k.  相似文献   

5.
Some properties of the spectrum of graphs   总被引:3,自引:0,他引:3  
Let G be a graph and denote by Q(G)=D(G) A(G),L(G)=D(G)-A(G) the sum and the difference between the diagonal matrix of vertex degrees and the adjacency matrix of G,respectively. In this paper,some properties of the matrix Q(G)are studied. At the same time,anecessary and sufficient condition for the equality of the spectrum of Q(G) and L(G) is given.  相似文献   

6.
Let 〈G, +〉 be a finite (not necessarily abelian) group. Then M0(G) := {f : GG| f (0) = 0} is a near-ring, i.e., a group which is also closed under composition of functions. In Theorem 4.1 we give lower and upper bounds for the fraction of the bijections which generate the near-ring M0(G). From these bounds we conclude the following: If G has few involutions and the order of G is large, then a high fraction of the bijections generate the near-ring M0(G). Also the converse holds: If a high fraction of the bijections generate M0(G), then G has few involutions (compared to the order of G). Received: 10 January 2005  相似文献   

7.
The square G2 of a graph G is the graph with the same vertex set G and with two vertices adjacent if their distance in G is at most 2. Thomassen showed that every planar graph G with maximum degree Δ(G) = 3 satisfies χ(G2) ≤ 7. Kostochka and Woodall conjectured that for every graph, the list‐chromatic number of G2 equals the chromatic number of G2, that is, χl(G2) = χ(G2) for all G. If true, this conjecture (together with Thomassen's result) implies that every planar graph G with Δ(G) = 3 satisfies χl(G2) ≤ 7. We prove that every connected graph (not necessarily planar) with Δ(G) = 3 other than the Petersen graph satisfies χl(G2) ≤8 (and this is best possible). In addition, we show that if G is a planar graph with Δ(G) = 3 and girth g(G) ≥ 7, then χl(G2) ≤ 7. Dvo?ák, ?krekovski, and Tancer showed that if G is a planar graph with Δ(G) = 3 and girth g(G) ≥ 10, then χl(G2) ≤6. We improve the girth bound to show that if G is a planar graph with Δ(G) = 3 and g(G) ≥ 9, then χl(G2) ≤ 6. All of our proofs can be easily translated into linear‐time coloring algorithms. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 65–87, 2008  相似文献   

8.
Let γ(G) and ir(G) denote the domination number and the irredundance number of a graph G, respectively. Allan and Laskar [Proc. 9th Southeast Conf. on Combin., Graph Theory & Comp. (1978) 43–56] and Bollobás and Cockayne [J. Graph Theory (1979) 241–249] proved independently that γ(G) < 2ir(G) for any graph G. For a tree T, Damaschke [Discrete Math. (1991) 101–104] obtained the sharper estimation 2γ(T) < 3ir(T). Extending Damaschke's result, Volkmann [Discrete Math. (1998) 221–228] proved that 2γ(G) ≤ 3ir(G) for any block graph G and for any graph G with cyclomatic number μ(G) ≤ 2. Volkmann also conjectured that 5γ(G) < 8ir(G) for any cactus graph. In this article we show that if G is a block-cactus graph having π(G) induced cycles of length 2 (mod 4), then γ(G)(5π(G) + 4) ≤ ir(G)(8π(G) + 6). This result implies the inequality 5γ(G) < 8ir(G) for a block-cactus graph G, thus proving the above conjecture. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 139–149, 1998  相似文献   

9.
Let G be a graph such that none of its components is bipartite. We describe the facets of the cone generated by the columns of the incidence matrix of G. Let k[G] be the subring generated by the monomials of degree two defining the edges of G, where k is a field. Some estimates for the a-invariant of k[G] are shown when G is the cone of a normal connected non bipartite graph or G is the join of two normal connected non bipartite graphs. Received: 24 July 1997 / Revised version: 3 March 1998  相似文献   

10.
《代数通讯》2013,41(12):4785-4794
Abstract

Let ω(G) denote the number of orbits on the finite group G under the action of Aut(G). Using the classification of finite simple groups, we prove that for any positive integer n, there is only a finite number of (non-abelian) finite simple groups G satisfying ω(G) ≤ n. Then we classify all finite simple groups G such that ω(G) ≤ 17. The latter result was obtained by computational means, using the computer algebra system GAP.  相似文献   

11.
In the following,G denotes a finite group,r(G) the number of conjugacy classes ofG, β(G) the number of minimal normal subgroups ofG andα(G) the number of conjugate classes ofG not contained in the socleS(G). Let Φ j = {G|β(G) =r(G) −j}. In this paper, the family Φ11 is classified. In addition, from a simple inspection of the groups withr(G) =b conjugate classes that appear in ϒ j =1/11 Φ j , we obtain all finite groups satisfying one of the following conditions: (1)r(G) = 12; (2)r(G) = 13 andβ(G) > 1; …; (9)r(G) = 20 andβ(G) > 8; (10)r(G) =n andβ(G) =na with 1 ≦a ≦ 11, for each integern ≧ 21. Also, we obtain all finite groupsG with 13 ≦r(G) ≦ 20,β(G) ≦r(G) − 12, and satisfying one of the following conditions: (i) 0 ≦α(G) ≦ 4; (ii) 5 ≦α(G) ≦ 10 andS(G) solvable.  相似文献   

12.
Two graphs G1 and G2 of order n pack if there exist injective mappings of their vertex sets into [n], such that the images of the edge sets do not intersect. Sauer and Spencer proved that if Δ (G1) Δ (G2) < 0.5n, then G1 and G2 pack. In this note, we study an Ore-type analogue of the Sauer–Spencer Theorem. Let θ(G) = max{d(u) + d(v): uvE(G)}. We show that if θ(G1)Δ(G2) < n, then G1 and G2 pack. We also characterize the pairs (G1,G2) of n-vertex graphs satisfying θ(G1)Δ(G2) = n that do not pack. This work was supported in part by NSF grant DMS-0400498. The work of the first author was also partly supported by grant 05-01-00816 of the Russian Foundation for Basic Research.  相似文献   

13.
For a given snark G and a given edge e of G, let ψ(G, e) denote the nonnegative integer such that for a cubic graph conformal to G – {e}, the number of Tait colorings with three given colors is 18 · ψ(G, e). If two snarks G1 and G2 are combined in certain well‐known simple ways to form a snark G, there are some connections between ψ (G1, e1), ψ (G2, e2), and ψ(G, e) for appropriate edges e1, e2, and e of G1, G2, and G. As a consequence, if j and k are each a nonnegative integer, then there exists a snark G with an edge e such that ψ(G, e) = 2j · 3k. © 2005 Wiley Periodicals, Inc.  相似文献   

14.
Let t(G) be the number of spanning trees of a connected graph G, and let b(G) be the number of bases of the bicircular matroid B(G). In this paper we obtain bounds relating b(G) and t(G), and study in detail the case where G is a complete graph Kn or a complete bipartite graph Kn,m.Received April 25, 2003  相似文献   

15.
Let G be a finite group. Let p(G) denote the minimal degree of a faithful permutation representation ofG and let q(G) and c(G) denote the minimal degree of a faithful representation of G by quasi-permutation matrices over the rational and the complex numbers, respectively. Finally r(G) denotes the minimal degree of a faithful rational valued complex character of G. The purpose of this paper is to calculate p(G), q(G), c(G) and r(G) for the group SP(4,q). This revised version was published online in June 2006 with corrections to the Cover Date.  相似文献   

16.
For a pair of integers k, l≥0, a graph G is (k, l)‐colorable if its vertices can be partitioned into at most k independent sets and at most l cliques. The bichromatic number χb(G) of G is the least integer r such that for all k, l with k+l=r, G is (k, l)‐colorable. The concept of bichromatic numbers simultaneously generalizes the chromatic number χ(G) and the clique covering number θ(G), and is important in studying the speed of hereditary properties and edit distances of graphs. It is easy to see that for every graph G the bichromatic number χb(G) is bounded above by χ(G)+θ(G)?1. In this article, we characterize all graphs G for which the upper bound is attained, i.e., χb(G)=χ(G)+θ(G)?1. It turns out that all these graphs are cographs and in fact they are the critical graphs with respect to the (k, l)‐colorability of cographs. More specifically, we show that a cograph H is not (k, l)‐colorable if and only if H contains an induced subgraph G with χ(G)=k+1, θ(G)=l+1 and χb(G)=k+l+1. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 263–269, 2010  相似文献   

17.
The amenability of the Banach algebra L 1(G), the measure algebra M(G) and their second duals of a locally compact group have been considered by a number of authors. During these investigations it has been shown that L 1(G)** is amenable if and only if G is finite. If LUC (G)*, the dual of the space of left uniformly continuous functions on G, is amenable, then G is compact and M(G) is amenable. Finally, if M(G)** is amenable, then G is finite. The aim of this paper is to generalize all of the above results to the locally compact hypergroups.  相似文献   

18.
Let G be a finite group and let r?. An r-coloring of G is any mapping χ:G→{1,…,r}. Colorings χ and ψ are equivalent if there exists gG such that χ(xg?1) = ψ(x) for every xG. A coloring χ is symmetric if there exists gG such that χ(gx?1g) = χ(x) for every xG. Let Sr(G) denote the number of symmetric r-colorings of G and sr(G) the number of equivalence classes of symmetric r-colorings of G. We count Sr(G) and sr(G) in the case where G is the dihedral group Dn.  相似文献   

19.
A set S of vertices of a graph G is a geodetic set if every vertex of G lies in an interval between two vertices from S. The size of a minimum geodetic set in G is the geodetic number g(G) of G. We find that the geodetic number of the lexicographic product G°H for a non-complete graph H lies between 2 and 3g(G). We characterize the graphs G and H for which g(G°H)=2, as well as the lexicographic products T°H that enjoy g(T°H)=3g(G), when T is isomorphic to a tree. Using a new concept of the so-called geodominating triple of a graph G, a formula that expresses the exact geodetic number of G°H is established, where G is an arbitrary graph and H a non-complete graph.  相似文献   

20.
Mohamed Asaad 《代数通讯》2013,41(6):2319-2330
Let G be a finite group. A subgroup H of G is said to be weakly s-supplemented in G if there exists a subgroup K of G such that G = HK and HK ≤ H s G , where H s G is the subgroup of H generated by all those subgroups of H which are s-quasinormal in G. In this article, we investigate the structure of G under the assumption that some families of subgroups of G are weakly s-supplemented in G. Some recent results are generalized.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号