On thel-connectivity of a graph

For an integerl 2, thel-connectivity of a graphG is the minimum number of vertices whose removal fromG produces a disconnected graph with at leastl components or a graph with fewer thanl vertices. A graphG is (n, l)-connected if itsl-connectivity is at leastn. Several sufficient conditions for a graph to be (n, l)-connected are established. IfS is a set ofl( 3) vertices of a graphG, then anS-path ofG is a path between distinct vertices ofS that contains no other vertices ofS. TwoS-paths are said to be internally disjoint if they have no vertices in common, except possibly end-vertices. For a given setS ofl 2 vertices of a graphG, a sufficient condition forG to contain at leastn internally disjointS-paths, each of length at most 2, is established.     

Group Weighted Matchings in Bipartite Graphs

Let G be a bipartite graph with bicoloration {A, B}, |A| = |B|, and let w : E(G) K where K is a finite abelian group with k elements. For a subset S E(G) let . A Perfect matching M E(G) is a w-matching if w(M) = 1.A characterization is given for all w's for which every perfect matching is a w-matching.It is shown that if G = K _k+1,k+1 then either G has no w-matchings or it has at least 2 w-matchings.If K is the group of order 2 and deg(a) d for all a A, then either G has no w-matchings, or G has at least (d – 1)! w-matchings.R. Meshulam: Research supported by a Technion V.P.R. Grant No. 100-854.     

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⁴).     

The partition dimension of circulant graphs

Let Π = {S₁, S₂, . . . , S_k} be an ordered partition of the vertex set V (G) of a graph G. The partition representation of a vertex v ∈ V (G) with respect to Π is the k-tuple r(v|Π) = (d(v, S₁), d(v, S₂), . . . , d(v, S_k)), where d(v, S) is the distance between v and a set S. If for every pair of distinct vertices u, v ∈ V (G), we have r(u|Π) ≠ r(v|Π), then Π is a resolving partition and the minimum cardinality of a resolving partition of V (G) is called the partition dimension of G. We study the partition dimension of circulant graphs, which are Cayley graphs of cyclic groups. Grigorious et al. [On the partition dimension of circulant graphs] proved that pd(C_n(1, 2, . . . , t)) ≥ t + 1 for n ≥ 3. We disprove this statement by showing that if t ≥ 4 is even, then there exists an infinite set of values of n, such that . We also present exact values of the partition dimension of circulant graphs with 3 generators.     

An Analogue of Hajós' Theorem for the Circular Chromatic Number (II)

This paper designs a set of graph operations, and proves that for 2k/d<3, starting from K_k/_d, by repeatedly applying these operations, one can construct all graphs G with _c(G)k/d. Together with the result proved in [20], where a set of graph operations were designed to construct graphs G with _c(G)k/d for k/d3, we have a complete analogue of Hajós' Theorem for the circular chromatic number. This research was partially supported by the National Science Council under grant NSC 89-2115-M-110-003     

Essential independent sets and long cycles

An independent set S of a graph G is said to be essential if S has a pair of vertices that are distance two apart in G. For SV(G) with S≠, let Δ(S)=max{d_G(x)|xS}. We prove the following theorem. Let k2 and let G be a k-connected graph. Suppose that Δ(S)d for every essential independent set S of order k. Then G has a cycle of length at least min{|G|,2d}. This generalizes a result of Fan.     

Centers to centroids in graphs

For S ? V(G) the S-center and S-centroid of G are defined as the collection of vertices u ∈ V(G) that minimize e_s(u) = max {d(u, v): v ∈ S} and d_s(u) = ∑_u∈S d(u, v), respectively. This generalizes the standard definition of center and centroid from the special case of S = V(G). For 1 ? k ?|V(G)| and u ∈ V(G) let r_k(u) = max {∑_s∈S d(u, s): S ? V(G), |S| = k}. The k-centrum of G, denoted C(G; k), is defined to be the subset of vertices u in G for which r_k(u) is a minimum. This also generalizes the standard definitions of center and centroid since C(G; 1) is the center and C(G; |V(G)|) is the centroid. In this paper the structure of these sets for trees is examined. Generalizations of theorems of Jordan and Zelinka are included.     

Isoperimetric inequalities in potential theory

Given a non-empty bounded domainG in ⁿ ,n2, letr ₀(G) denote the radius of the ballG ₀ having center 0 and the same volume asG. The exterior deficiencyd _e (G) is defined byd _e (G)=r _e (G)/r ₀(G)–1 wherer _e (G) denotes the circumradius ofG. Similarlyd _i (G)=1–r _i (G)/r ₀(G) wherer _i (G) is the inradius ofG. Various isoperimetric inequalities for the capacity and the first eigenvalue ofG are shown. The main results are of the form CapG(1+cf(d _e (G)))CapG ₀ and ₁(G)(1+cf(d _i (G)))₁(G ₀),f(t)=t ³ ifn=2,f(t)=t ³/(ln 1/t) ifn=3,f(t)=t ^(n+3)/2 ifn4 (for convex G and small deficiencies ifn3).     

A finiteness theorem for maximal independent sets

Denote bymi(G) the number of maximal independent sets ofG. This paper studies the setS(k) of all graphsG withmi(G) = k and without isolated vertices (exceptG K ₁) or duplicated vertices. We determineS(1), S(2), andS(3) and prove that |V(G)| 2 ^k–1 +k – 2 for anyG inS(k) andk 2; consequently,S(k) is finite for anyk. Supported in part by the National Science Council under grant NSC 83-0208-M009-050     

Fan-type theorem for path-connectivity

A graphG is said to bek-path-connected if every pair of distinct vertices inG are joined by a path of length at leastk. We prove that if max{deg _G ^x , deg _G ^y }k for every pair of verticesx,y withd _G (x,y)=2 in a 2-connected graphG, whered _G (x,y) is the distance betweenx andy inG, thenG isk-path-connected.     

The total chromatic number of regular graphs of high degree

The total chromatic number χT (G) of a graph G is the minimum number of colors needed to color the edges and the vertices of G so that incident or adjacent elements have distinct colors. We show that if G is a regular graph and d(G) 32 |V (G)| + 263 , where d(G) denotes the degree of a vertex in G, then χT (G) d(G) + 2.     

On Cycles in 3-Connected Graphs

 Let G be a 3-connected graph of order n and S a subset of vertices. Denote by δ(S) the minimum degree (in G) of vertices of S. Then we prove that the circumference of G is at least min{|S|, 2δ(S)} if the degree sum of any four independent vertices of S is at least n+6. A cycle C is called S-maximum if there is no cycle C ^′ with |C ^′∩S|>|C∩S|. We also show that if ∑⁴ _i=1 d(a _i)≥n+3+|⋂⁴ _i=1 N(a _i)| for any four independent vertices a ₁, a ₂, a ₃, a ₄ in S, then G has an S-weak-dominating S-maximum cycle C, i.e. an S-maximum cycle such that every component in G−C contains at most one vertex in S. Received: March 9, 1998 Revised: January 7, 1999     

Thep-intersection number of a complete bipartite graph and orthogonal double coverings of a clique

Thep-intersection graph of a collection of finite sets {S _i } _i=1 ⁿ is the graph with vertices 1, ...,n such thati, j are adjacent if and only if |S _i S _j |p. Thep-intersection number of a graphG, herein denoted _p (G), is the minimum size of a setU such thatG is thep-intersection graph of subsets ofU. IfG is the complete bipartite graphK _n,n andp2, then _p (K _{n, n} )(n ²+(2p–1)n)/p. Whenp=2, equality holds if and only ifK _n has anorthogonal double covering, which is a collection ofn subgraphs ofK _n , each withn–1 edges and maximum degree 2, such that each pair of subgraphs shares exactly one edge. By construction,K _n has a simple explicit orthogonal double covering whenn is congruent modulo 12 to one of {1, 2, 5, 7, 10, 11}.Research supported in part by ONR Grant N00014-5K0570.     

Independent sets,cliques and hamiltonian graphs

LetG be ak-connected (k 2) graph onn vertices. LetS be an independent set ofG. S is called essential if there exist two distinct vertices inS which have a common neighbor inG. LetV _r, be a clique which is a complete subgraph ofG. In this paper it is proven that if every essential independent setS ofk + 1 vertices satisfiesS V _r , thenG is hamiltonian, orG{u} is hamiltonian for someu V _r, orG is one of three classes of exceptional graphs. Our theorem generalizes several well-known theorems.     

Minimal presentations for certain group extensions

IfG is a finite group thend(G) denotes the minimal number of generators ofG. IfH andK are groups then the extension, 1 →H →G →K → 1, is called an outer extension ofK byH ifd(G)=d(H)+d(K). Let be the class of groups containing all finitep-groupsG which has a presentation withd(G) = dimH ¹(G,z _p ) generators andr(G)=dimH ² (G,Z _p ) relations: in this article it is shown that ifK is a non cyclic group belonging to andH is a finite abelian p-group then any outer extension ofK byH belongs to .     

Root Sublattices and Torus-Restriction of Prehomogeneous Vector Spaces Associated with Dynkin Quivers

For a Dynkin quiver Γ with r vertices, a subset S of the vertices of Γ, and an r-tuple d = (d⁽¹⁾, d⁽²⁾,…, d^(r)) of positive integers, we define a “torus-restricted” representation (G_S, R _d (Γ)) in natural way. Here we put G_S = G₁ × G₂ × … ×G_r, where each G_i is either SL(d⁽ⁱ⁾) or GL(d⁽ⁱ⁾) according to S containing i or not. In this paper, for a prescribed torus-restriction S, we give a necessary and sufficient condition on d that R _d (Γ) has only finitely many G_S-orbits. This can be paraphrased as a condition whether or not d is contained in a certain lattice spanned by positive roots of Γ. We also discuss the prehomogeneity of (G_S, R _d (Γ)).     

A measuring argument for finite permutation groups

LetG be a finite transitive permutation group on a finite setS. LetA be a nonempty subset ofS and denote the pointwise stabilizer ofA inG byC _G (A). Our main result is the following inequality: [G :C _G (A)]≥|G|^|A|/|S|. This paper is a part of the author’s Ph.D. thesis research, carried out at Tel Aviv University under the supervision of Professor Marcel Herzog.     

A sufficient degree condition for a graph to contain all trees of size <Emphasis Type="Italic">k</Emphasis>

The Erdős-Sós conjecture says that a graph G on n vertices and number of edges e(G) > n(k− 1)/2 contains all trees of size k. In this paper we prove a sufficient condition for a graph to contain every tree of size k formulated in terms of the minimum edge degree ζ(G) of a graph G defined as ζ(G) = min{d(u) + d(v) − 2: uv ∈ E(G)}. More precisely, we show that a connected graph G with maximum degree Δ(G) ≥ k and minimum edge degree ζ(G) ≥ 2k − 4 contains every tree of k edges if d _G (x) + d _G (y) ≥ 2k − 4 for all pairs x, y of nonadjacent neighbors of a vertex u of d _G (u) ≥ k.     

Hadwiger Number and the Cartesian Product of Graphs

The Hadwiger number η(G) of a graph G is the largest integer n for which the complete graph K _n on n vertices is a minor of G. Hadwiger conjectured that for every graph G, η(G) ≥ χ(G), where χ(G) is the chromatic number of G. In this paper, we study the Hadwiger number of the Cartesian product of graphs. As the main result of this paper, we prove that for any two graphs G ₁ and G ₂ with η(G ₁) = h and η(G ₂) = l. We show that the above lower bound is asymptotically best possible when h ≥ l. This asymptotically settles a question of Z. Miller (1978). As consequences of our main result, we show the following:

On the Structure of Graphs with Bounded Asteroidal Number

 A set A⊆V of the vertices of a graph G=(V,E) is an asteroidal set if for each vertex a∈A, the set A\{a} is contained in one component of G−N[a]. The maximum cardinality of an asteroidal set of G, denoted by an (G), is said to be the asteroidal number of G. We investigate structural properties of graphs of bounded asteroidal number. For every k≥1, an (G)≤k if and only if an (H)≤k for every minimal triangulation H of G. A dominating target is a set D of vertices such that D∪S is a dominating set of G for every set S such that G[D∪S] is connected. We show that every graph G has a dominating target with at most an (G) vertices. Finally, a connected graph G has a spanning tree T such that d _T (x,y)−d _G (x,y)≤3·|D|−1 for every pair x,y of vertices and every dominating target D of G. Received: July 3, 1998 Final version received: August 10, 1999