The wiener index of graphs of arbitrary girth and their line graphs

We consider the invariant W(G) of a simple connected undirected graph G which is equal to the sum of distances between all pairs of its vertices in the natural metric (the Wiener index). We show that, for every g ≥ 5, there is a planar graph G of girth g satisfying W(L(G)) = W(G), where L(G) is the line graph of G.     

Closed Separator Sets

A smallest separator in a finite, simple, undirected graph G is a set S ⊆ V (G) such that G–S is disconnected and |S|=κ(G), where κ(G) denotes the connectivity of G. A set S of smallest separators in G is defined to be closed if for every pair S,T ∈ S, every component C of G–S, and every component S of G–T intersecting C either X(C,D) := (V (C) ∩ T) ∪ (T ∩ S) ∪ (S ∩ V (D)) is in S or |X(C,D)| > κ(G). This leads, canonically, to a closure system on the (closed) set of all smallest separators of G. A graph H with is defined to be S-augmenting if no member of S is a smallest separator in G ∪ H:=(V (G) ∪ V (H), E(G) ∪ E(H)). It is proved that if S is closed then every minimally S-augmenting graph is a forest, which generalizes a result of Jordán. Several applications are included, among them a generalization of a Theorem of Mader on disjoint fragments in critically k-connected graphs, a Theorem of Su on highly critically k-connected graphs, and an affirmative answer to a conjecture of Su on disjoint fragments in contraction critically k-connected graphs of maximal minimum degree.     

Generalization of a theorem of Gonchar

Let X and Y be two complex manifolds, let D⊂X and G⊂Y be two nonempty open sets, let A (resp. B) be an open subset of ∂D (resp. ∂G), and let W be the 2-fold cross ((D∪A)×B)∪(A×(B∪G)). Under a geometric condition on the boundary sets A and B, we show that every function locally bounded, separately continuous on W, continuous on A×B, and separately holomorphic on (A×G)∪(D×B) “extends” to a function continuous on a “domain of holomorphy” and holomorphic on the interior of .     

Normal Cayley graphs of finite groups

LetG be a finite group and let S be a nonempty subset of G not containing the identity element 1. The Cayley (di) graph X = Cay(G, S) of G with respect to S is defined byV (X)=G, E (X)={(g,sg)|g∈G, s∈S} A Cayley (di) graph X = Cay (G,S) is said to be normal ifR(G) ◃A = Aut (X). A group G is said to have a normal Cayley (di) graph if G has a subset S such that the Cayley (di) graph X = Cay (G, S) is normal. It is proved that every finite group G has a normal Cayley graph unlessG≅ℤ₄×ℤ₂ orG≅Q ₈×ℤ ₂ ^r (r⩾0) and that every finite group has a normal Cayley digraph, where Z_m is the cyclic group of orderm and Q₈ is the quaternion group of order 8. Project supported by the National Natural Science Foundation of China (Grant No. 10231060) and the Doctorial Program Foundation of Institutions of Higher Education of China.     

On the prime graph of <Emphasis Type="Italic">PSL</Emphasis>(2, <Emphasis Type="Italic">p</Emphasis>) where <Emphasis Type="Italic">p</Emphasis> > 3 is a prime number

Let G be a finite group. We define the prime graph Γ(G) as follows. The vertices of Γ(G) are the primes dividing the order of G and two distinct vertices p, q are joined by an edge if there is an element in G of order pq. Recently M. Hagie [5] determined finite groups G satisfying Γ(G) = Γ(S), where S is a sporadic simple group. Let p > 3 be a prime number. In this paper we determine finite groups G such that Γ(G) = Γ(PSL(2, p)). As a consequence of our results we prove that if p > 11 is a prime number and p ≢ 1 (mod 12), then PSL(2, p) is uniquely determined by its prime graph and so these groups are characterizable by their prime graph. The third author was supported in part by a grant from IPM (No. 84200024).     

Groups with an element permuting with finitely many of its conjugates

We study the problem as to which is the cardinality of connected components of the graph Γ_α, defined as follows. Let G be a group and a an element of G. The vertex set V(Γ_α) of the graph is the conjugacy class of elements,Cl _G(a), and two vertices x and y of the graph Γ_α are bridged by an edge iff x=y. If the intersectionC _G(a)∩Cl _G(a) is finite, Γ_α is locally finite. We prove that connected components of the locally finite graph Γ_α are finite in some classes of groups. Supported by RFFR grant No. 94-01-01084. Translated fromAlgebra i Logika, Vol. 35, No. 5, pp. 543–551, September–October, 1996.     

Partial Parity (g,f )-Factors and Subgraphs Covering Given Vertex Subsets

 Let G be a graph and W a subset of V(G). Let g,f:V(G)→Z be two integer-valued functions such that g(x)≤f(x) for all x∈V(G) and g(y)≡f(y) (mod 2) for all y∈W. Then a spanning subgraph F of G is called a partial parity (g,f)-factor with respect to W if g(x)≤deg _F (x)≤f(x) for all x∈V(G) and deg _F (y)≡f(y) (mod 2) for all y∈W. We obtain a criterion for a graph G to have a partial parity (g,f)-factor with respect to W. Furthermore, by making use of this criterion, we give some necessary and sufficient conditions for a graph G to have a subgraph which covers W and has a certain given property. Received: June 14, 1999?Final version received: August 21, 2000     

On Partially Ordered Semigroups and an Abstract Set-Difference

In this paper we prove the independence of a system of five axioms (S1)–(S5), which was proposed in the book of Pallaschke and Urbański (Pairs of Compact Convex Sets, vol. 548, Kluwer Academic Publishers, Dordrecht, 2002) for partially ordered commutative semigroups. These five axioms (S1)–(S5) are stated in the introduction below. A partially ordered commutative semigroup satisfying these axioms is called a F-semigroup. By the use of a further axiom (S6) we define an abstract difference for the elements of a F-semigroup and prove some basic properties. The most interesting example of a F-semigroup are the nonempty compact convex sets of a topological vector space endowed with the Minkowski sum as operation and the inclusion as partial order. In Section 4 we apply the abstract difference to the problem of minimality of convex fractions. Dedicated to Boris Mordukhovich in honour of his 60th birthday.     

Graphs of actions on R-trees

LetG be a finitely generated group acting on anR-treeT. First assume that the action is free, and minimal (there is no proper invariant subtree), or more generally that it satisfies a certain finiteness condition. Then it may be described as agraph of transitive actions: the action may be recovered from a finite graph, together with additional data; in particular, every vertexv carries an action (G _v, T_v) whose orbits are dense. For the action (G, T), it follows for instance that the closure of any orbit is a discrete union of closed subtrees: it cannot meet a segment in a Cantor set. Now let ℓ be the length function for an arbitrary action ofG. For ɛ>0 small enough, the subgroupG(ɛ)⊂G generated by elementsg withg is independent of ɛ, andG/G(ɛ) is free. Several interpretations are given for the rank ofG/G(ɛ).     

Some results on spanning trees

Some structures of spanning trees with many or less leaves in a connected graph are determined.We show（1） a connected graph G has a spanning tree T with minimum leaves such that T contains a longest path,and（2） a connected graph G on n vertices contains a spanning tree T with the maximum leaves such that Δ（G） =Δ（T） and the number of leaves of T is not greater than n D（G）＋1,where D（G） is the diameter of G.     

On Compact Graphs

Let G be a finite simple graph with adjacency matrix A, and let P（A） be the convex closure of the set of all permutation matrices commuting with A. G is said to be compact if every doubly stochastic matrix which commutes with A is in P（A）. In this paper, we characterize 3-regular compact graphs and prove that if G is a connected regular compact graph, G - v is also compact, and give a family of almost regular compact connected graphs.     

（g, f）-Factorizations Randomly Orthogonal to a Subgraph in Graphs

Let G be a graph with vertex set V(G) and edge set E(G) and let g and f be two integervalued functions defined on V(G) such that 2k - 2 ≤g(x)≤f(x) for all x∈V(G). Let H be a subgraph of G with mk edges. In this paper, it is proved that every (mg m-1,mf-m 1)-graph G has (g, f)-factorizations randomly k-orthogonal to H under some special conditions.     

A finiteness theorem for primal extensions

A set W⊆V(G) is called homogeneous in a graph G if 2?|W|?|V(G)|-1, and N(x)?W=N(y)?W for each x,y∈W. A graph without homogeneous sets is called prime. A graph H is called a (primal) extension of a graph G if G is an induced subgraph of H, and H is a prime graph. An extension H of G is minimal if there are no extensions of G in the set ISub(H)?{H}. We denote by Ext(G) the set of all minimal extensions of a graph G.We investigate the following problem: find conditions under which Ext(G) is a finite set. The main result of Giakoumakis (Discrete Math. 177 (1997) 83-97) is the following sufficient condition.

Theorem. If every homogeneous set of G has exactly two vertices thenExt(G)is a finite set.     

Zero-sum problems with congruence conditions

For a finite abelian group G and a positive integer d, let s _dℕ(G) denote the smallest integer ℓ∈ℕ₀ such that every sequence S over G of length |S|≧ℓ has a nonempty zero-sum subsequence T of length |T|≡0 mod d. We determine s _dℕ(G) for all d≧1 when G has rank at most two and, under mild conditions on d, also obtain precise values in the case of p-groups. In the same spirit, we obtain new upper bounds for the Erdős–Ginzburg–Ziv constant provided that, for the p-subgroups G _p of G, the Davenport constant D(G _p ) is bounded above by 2exp  (G _p )−1. This generalizes former results for groups of rank two.     

Forests and score vectors

Thescore vector of a labeled digraph is the vector of out-degrees of its vertices. LetG be a finite labeled undirected graph without loops, and let σ(G) be the set of distinct score vectors arising from all possible orientations ofG. Let ϕ(G) be the set of subgraphs ofG which are forests of labeled trees. We display a bijection between σ(G) and ϕ(G). Supported in part by ONR Contract N00014-76-C-0366.     

Real loci of based loop groups

Let (G, K) be a Riemannian symmetric pair of maximal rank, where G is a compact simply connected Lie group and K is the fixed point set of an involutive automorphism σ. This induces an involutive automorphism τ of the based loop space Ω(G). There exists a maximal torus T ⊂ G such that the canonical action of T × S ¹ on Ω(G) is compatible with τ (in the sense of Duistermaat). This allows us to formulate and prove a version of Duistermaat’s convexity theorem. Namely, the images of Ω(G) and Ω(G) ^τ (fixed point set of τ) under the T × S ¹ moment map on Ω(G) are equal. The space Ω(G) ^τ is homotopy equivalent to the loop space Ω(G/K) of the Riemannian symmetric space G/K. We prove a stronger form of a result of Bott and Samelson which relates the cohomology rings with coefficients in \mathbbZ₂ {\mathbb{Z}_2} of Ω(G) and Ω(G/K). Namely, the two cohomology rings are isomorphic, by a degree-halving isomorphism (Bott and Samelson [BS] had proved that the Betti numbers are equal). A version of this theorem involving equivariant cohomology is also proved. The proof uses the notion of conjugation space in the sense of Hausmann, Holm, and Puppe [HHP].     

On Optimal Orientations of Cartesian Products of Trees

. Let d(D) (resp., d(G)) denote the diameter and r(D) (resp., r(G)) the radius of a digraph D (resp., graph G). Let G×H denote the cartesian product of two graphs G and H. An orientation D of G is said to be (r, d)-invariant if r(D)=r(G) and d(D)=d(G). Let {T _i }, i=1,…,n, where n≥2, be a family of trees. In this paper, we show that the graph ∏ _{i =1} ⁿ T _i admits an (r, d)-invariant orientation provided that d(T ₁)≥d(T ₂)≥4 for n=2, and d(T ₁)≥5 and d(T ₂)≥4 for n≥3. Received: July 30, 1997 Final version received: April 20, 1998     

The diameter of paired-domination vertex critical graphs

In this paper we continue the study of paired-domination in graphs introduced by Haynes and Slater (Networks 32 (1998), 199–206). A paired-dominating set of a graph G with no isolated vertex is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number of G, denoted by γ _pr(G), is the minimum cardinality of a paired-dominating set of G. The graph G is paired-domination vertex critical if for every vertex v of G that is not adjacent to a vertex of degree one, γ _pr(G − v) < γ _pr(G). We characterize the connected graphs with minimum degree one that are paired-domination vertex critical and we obtain sharp bounds on their maximum diameter. We provide an example which shows that the maximum diameter of a paired-domination vertex critical graph is at least 3/2 (γ _pr(G) − 2). For γ _pr(G) ⩽ 8, we show that this lower bound is precisely the maximum diameter of a paired-domination vertex critical graph. The first author was supported in part by the South African National Research Foundation and the University of KwaZulu-Natal, the second author was supported by the Natural Sciences and Engineering Research Council of Canada.     

One-regular Normal Cayley Graphs on Dihedral Groups of Valency 4 or 6 with Cyclic Vertex Stabilizer

A graph G is one-regular if its automorphism group Aut（G） acts transitively and semiregularly on the arc set. A Cayley graph Cay（Г, S） is normal if Г is a normal subgroup of the full automorphism group of Cay（Г, S）. Xu, M. Y., Xu, J. （Southeast Asian Bulletin of Math., 25, 355-363 （2001）） classified one-regular Cayley graphs of valency at most 4 on finite abelian groups. Marusic, D., Pisanski, T. （Croat. Chemica Acta, 73, 969-981 （2000）） classified cubic one-regular Cayley graphs on a dihedral group, and all of such graphs turn out to be normal. In this paper, we classify the 4-valent one-regular normal Cayley graphs G on a dihedral group whose vertex stabilizers in Aut（G） are cyclic. A classification of the same kind of graphs of valency 6 is also discussed.