On the relations of graph parameters and its total parameters

In this paper we get some relations between α（G）, α＇（G）, β（G）, β＇（G） and αT（G）, βT（G）. And all bounds in these relations are best possible, where α（G）, α＇（G）,/3（G）, β（G）, αT（G） and βT（G） are the covering number, edge-covering number, independent number, edge-independent number （or matching number）, total covering number and total independent number, respectively.     

Joint continuity of multiplication on the dual of the left uniformly continuous functions

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.     

Amenability of the Second Dual of Hypergroup Algebras

The amenability of the Banach algebra L ¹(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 ¹(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.     

Some extremal results in cochromatic and dichromatic theory

For a graph G, the cochromatic number of G, denoted z(G), is the least m for which there is a partition of the vertex set of G having order m. where each part induces a complete or empty graph. We show that if {G_n} is a family of graphs where G_n has o(n² log²(n)) edges, then z(G_n) = o(n). We turn our attention to dichromatic numbers. Given a digraph D, the dichromatic number of D is the minimum number of parts the vertex set of D must be partitioned into so that each part induces an acyclic digraph. Given an (undirected) graph G, the dichromatic number of G, denoted d(G), is the maximum dichromatic number of all orientations of G. Let m be an integer; by d(m) we mean the minimum size of all graphs G where d(G) = m. We show that d(m) = θ(m² ln²(m)).     

Solvable line-transitive automorphism groups of finite linear spaces

Let S be a finite linear space, and letG be a group of automorphisms of S. IfG is soluble and line-transitive, then for a givenk but a finite number of pairs of (S, G),S hasv= p ⁿ points andG ⩽AΓL(1,p ⁿ ).     

Tension polynomials of graphs

The tension polynomial F_G(k) of a graph G, evaluating the number of nowhere‐zero ?_k‐tensions in G, is the nontrivial divisor of the chromatic polynomial χ_G(k) of G, in that χ_G(k) = k^c(G)F_G(k), where c(G) denotes the number of components of G. We introduce the integral tension polynomial I_G(k), which evaluates the number of nowhere‐zero integral tensions in G with absolute values smaller than k. We show that 2^r(G)F_G(k)≥I_G(k)≥ (r(G)+1)F_G(k), where r(G)=|V(G)|?c(G), and, for every k>1, F_G(k+1)≥ F_G(k)˙k / (k?1) and I_G(k+1)≥I_G(k)˙k/(k?1). © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 137–146, 2002     

Independence number,connectivity, and r-factors

We show that if r ? 1 is an odd integer and G is a graph with |V(G)| even such that k(G) ? (r + 1)²/2 and (r + 1)²α(G) ? 4rk(G), then G has an r-factor; if r ? 2 is even and G is a graph with k(G) ? r(r + 2)/2 and (r + 2)α(G) ? 4k(G), then G has an r-factor (where k(G) and α(G) denote the connectivity and the independence number of G, respectively).     

A note on the bichromatic numbers of graphs

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     

Homogeneous trees are bilipschitz equivalent

We prove that any two locally finite homogeneous trees with valency greater than 3 are bilipschitz equivalent. This implies that the quotienth ¹(G)/h ^k (G), whereh ^k (G) is thekthL ₂-Betti number ofG, is not a quasi-isometry invariant.     

On the computation of the projective surgery obstruction groups

The computation of the projective surgery obstruction groupsL _n ^p (ZG), forG a hyperelementary finite group, is reduced to standard calculations in number theory, mostly involving class groups. Both the exponent of the torsion subgroup and the precise divisibility of the signatures are determined. ForG a 2-hyperelementary group, theL _n ^p (ZG) are detected by restriction to certain subquotients ofG, and a complete set of invariants is given for oriented surgery obstructions.Partially supported by NSERC grant A4000.Partially supported by NSF grant DMS-8610730(1) and the Danish Research Council.     

On the number of colorings of a snark minus an edge

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 G₁ and G₂ are combined in certain well‐known simple ways to form a snark G, there are some connections between ψ (G₁, e₁), ψ (G₂, e₂), and ψ(G, e) for appropriate edges e₁, e₂, and e of G₁, G₂, 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) = 2^j · 3^k. © 2005 Wiley Periodicals, Inc.     

The geodetic numbers of graphs and digraphs

For every two vertices u and v in a graph G,a u-v geodesic is a shortest path between u and v.Let I(u,v)denote the set of all vertices lying on a u-v geodesic.For a vertex subset S,let I(S) denote the union of all I(u,v)for u,v∈S.The geodetic number g(G)of a graph G is the minimum cardinality of a set S with I(S)=V(G).For a digraph D,there is analogous terminology for the geodetic number g(D).The geodetic spectrum of a graph G,denoted by S(G),is the set of geodetic numbers of all orientations of graph G.The lower geodetic number is g~-(G)=minS(G)and the upper geodetic number is g~ (G)=maxS(G).The main purpose of this paper is to study the relations among g(G),g~-(G)and g~ (G)for connected graphs G.In addition,a sufficient and necessary condition for the equality of g(G)and g(G×K_2)is presented,which improves a result of Chartrand,Harary and Zhang.     

On the Upper Bounds of the Numbers of Perfect Matchings in Graphs with Given Parameters

Let φ(G),κ(G),α(G),χ(G),cl(G),diam(G)denote the number of perfect matchings,connectivity,independence number,chromatic number,clique number and diameter of a graph G,respectively.In this note,by constructing some extremal graphs,the following extremal problems are solved:1.max{φ(G):|V(G)|=2n,κ(G)≤k}=k[(2n-3)!!],2.max{φ(G):|V(G)|=2n,α(G)≥k}=[multiply from i=0 to k-1(2n-k-i)[(2n-2k-1)!!],3.max{φ(G):|V(G)|=2n,χ(G)≤k}=φ(T_(k,2n))T_(k,2n)is the Turán graph,that is a complete k-partite graphon 2n vertices in which all parts are as equal in size as possible,4.max{φ(G):|V(G)|=2n,cl(G)=2}=n1,5.max{φ(G):|V(G)|=2n,diam(G)≥2}=(2n-2)(2n-3)[(2n-5)!!],max{φ(G):|V(G)|=2n,diam(G)≥3}=(n-1)~2[(2n-5)!!].     

An upper bound on the size of a largest clique in a graph

A graph is point determining if distinct vertices have distinct neighborhoods. The nucleus of a point-determining graph is the set G^O of all vertices, v, such that G–v is point determining. In this paper we show that the size, ω(G), of a maximum clique in G satisfies ω(G) ? 2|π (G)^O|, where π(G) (the point determinant of G) is obtained from G by identifying vertices which have the same neighborhood.     

On the connectivity of unit distance graphs

For a number fieldK , consider the graphG(K^d), whose vertices are elements ofK ^d, with an edge between any two points at (Euclidean) distance 1. We show thatG(K²) is not connected whileG(K^d) is connected ford 5. We also give necessary and sufficient conditions for the connectedness ofG(K³) andG(K⁴).     

Minimal systems of arbitrary large mean topological dimension

Let G be a countable amenable group and P a polyhedron. The mean topological dimension mdim(X,G) of a subshift X ⊂ P ^G is a real number satisfying 0 ≤ mdim(X,G) ≤ dim(P), where dim(P) denotes the usual topological dimension of P. We give a construction of minimal subshifts X ⊂ P ^G with mean topological dimension arbitrarily close to dim(P).     

A characterization of domination perfect graphs

Let γ(G) and i(G) be the domination number and independent domination number of a graph G, respectively. Sumner and Moore [8] define a graph G to be domination perfect if γ(H) = i(H), for every induced subgraph H of G. In this article, we give a finite forbidden induced subgraph characterization of domination perfect graphs. Bollobás and Cockayne [4] proved an inequality relating γ(G) and i(G) for the class of K^1,k -free graphs. It is shown that the same inequality holds for a wider class of graphs.     

Quasi-permutation Representations of the Groups SU (3, q2) and PSU (3, q2)

A square matrix over the complex field with non-negative integral trace is called a quasi-permutation matrix. For a finite group G the minimal degree of a faithful permutation representation of G is denoted by p(G). The minimal degree of a faithful representation of G by quasi-permutation matrices over the rational and the complex numbers are denoted by q(G) and c(G) respectively. Finally r(G) denotes the minimal degree of a faithful rational valued complex character of G. In this paper p(G), q(G), c(G) and r(G) are calculated for the groups PSU (3, q²) and SU (3, q²).AMS Subject Classification (2000): 20C15     

Extension of Turán's Theorem to the 2-Stability Number

 Given a graph G with n vertices and stability number α(G), Turán's Theorem gives a lower bound on the number of edges in G. Furthermore, Turán has proved that the lower bound is only attained if G is the union of α(G) disjoint balanced cliques. We prove a similar result for the 2-stability number α₂(G) of G, which is defined as the largest number of vertices in a 2-colorable subgraph of G. Given a graph G with n vertices and 2-stability number α₂(G), we give a lower bound on the number of edges in G and characterize the graphs for which this bound is attained. These graphs are the union of isolated vertices and disjoint balanced cliques. We then derive lower bounds on the 2-stability number, and finally discuss the extension of Turán's Theorem to the q-stability number, for q>2. Received: July 21, 1999 Final version received: August 22, 2000 Present address: GERAD, 3000 ch. de la Cote-Ste-Catherine, Montreal, Quebec H3T 2A7, Canada. e-mail: Alain.Hertz@gerad.ca     

Strong Arens irregularity of Beurling algebras with a locally convex topology

Let G be a locally compact group with a weight function ω. Recently, we have shown that the Banach space L₀^∞ (G,1/ω) can be identified with the strong dual of L¹(G, ω)equipped with some locally convex topologies τ. Here we use this duality to introduce an Arens multiplication on (L¹(G, ω), τ)**, and prove that the topological center of (L¹(G, ω), τ)** is (L¹(G, ω); this enables us to conclude that (L¹(G, ω), τ) is Arens regular if and only if G is discrete. We also give a characterization for Arens regularity of L₀^∞ (G, 1/ω)¹. Received: 8 March 2005