Pancyclism in Chvátal-Erdös's graphs

LetG = (X, E) be a simple graph of ordern, of stability numberα and of connectivityk withα ≤ k. The Chvátal-Erdös's theorem [3] proves thatG is hamiltonian. We have investigated under these conditions what can be said about the existence of cycles of lengthl. We have obtained several results:

1. IfG ≠ K _k,k andG ≠ C ₅,G has aC _n?1 .
2. IfG ≠ C ₅, the girth ofG is at most four.
3. Ifα = 2 and ifG ≠ C ₄ orC ₅,G is pancyclic.
4. Ifα = 3 and ifG ≠ K _3,3,G has cycles of any length between four andn.
5. IfG has noC ₃,G has aC _n?2 .

     

Die Endlichen Polardreiseitgeometrien

LetG be a finite group which is generated by a subsetS of involutions satisfying the theorem of the three reflections: Ifa,b,x,y,z ∈ S, ab ≠ 1 and ifabx,aby,abz are involutions, thenxyz ∈ S. Assume thatS contains three elements which generate a four-group. IfS contains four elements of which no three have a product of order two, then one of the following occurs.

1. G?PGL(2,n), n≡1 (mod 2).
2. G?PSL(2,n), n≡1 (mod 2) and n≥5.
3. G?PSU(3,16).
4. G/Z(G)?PSL(2,9) with ¦Z(G)¦=3.

     

A note on the size of the nilpotent residual in finite groups

In this note it is proved that ${|G : Z(G)| < |G^\prime| \cdot |G^\mathcal{N}|}$ if G is a finite non-abelian group with ?? (G) = 1.     

Lower bounds on the number of maximal subgroups in a finite group

For a finite group G, let m(G) denote the set of maximal subgroups of G and π(G) denote the set of primes which divide |G|. When G is a cyclic group, an elementary calculation proves that |m(G)| = |π(G)|. In this paper, we prove lower bounds on |m(G)| when G is not cyclic. In general, ${|m(G)| \geq |\pi(G)|+p}$ | m ( G ) | ≥ | π ( G ) | + p , where ${p \in \pi(G)}$ p ∈ π ( G ) is the smallest prime that divides |G|. If G has a noncyclic Sylow subgroup and ${q \in \pi(G)}$ q ∈ π ( G ) is the smallest prime such that ${Q \in {\rm syl}_q(G)}$ Q ∈ syl q ( G ) is noncyclic, then ${|m(G)| \geq |\pi(G)|+q}$ | m ( G ) | ≥ | π ( G ) | + q . Both lower bounds are best possible.     

A relationship between bounds on the sum of squares of degrees of a graph

LetG = (V, E) be a simple graph withn vertices and e edges. Letdi be the degree of the ith vertex v_i ∈ V andm _i the average of the degrees of the vertices adjacent to vertexv _i ∈ V. It is known by Caen [1] and Das [2] that $\frac{{4e^2 }}{n} \leqslant d_1^2 + ... + d_n^2 \leqslant e max \{ d_j + m_j |v_j \in V\} \leqslant e\left( {\frac{{2e}}{{n - 1}} + n - 2} \right)$ . In general, the equalities do not hold in above inequality. It is shown that a graphG is regular if and only if $\frac{{4e^2 }}{n} = d_1^2 + ... + d_n^2 $ . In fact, it is shown a little bit more strong result that a graphG is regular if and only if $\frac{{4e^2 }}{n} = d_1^2 + ... + d_n^2 = e max \{ d_j + m_j |v_j \in V\} $ . For a graphG withn < 2 vertices, it is shown that G is a complete graphK _n if and only if $\frac{{4e^2 }}{n} = d_1^2 + ... + d_n^2 = e max \{ d_j + m_j |v_j \in V\} = e\left( {\frac{{2e}}{{n - 1}} + n - 2} \right)$ .     

Upper Bounds on the Paired Domination Subdivision Number of a Graph

A paired dominating set of a graph G with no isolated vertex is a dominating set S of vertices such that the subgraph induced by S in G 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 paired domination subdivision number ${{\rm sd}_{\gamma _{\rm pr}}(G)}$ is the minimum number of edges to be subdivided (each edge of G can be subdivided at most once) in order to increase the paired domination number. In this paper, we show that if G is a connected graph of order at least 4, then ${{\rm sd}_{\gamma _{\rm pr}}(G)\leq 2|V(G)|-5}$ . We also characterize trees T such that ${{\rm sd}_{\gamma _{\rm pr}}(T) \geq |V(T)| /2}$ .     

The binding number of a graph and its pancyclism

The binding number is an important parameter of a graph.The binding number of a graph G,bind (G),is the largest real number c such that|N(X)|=min(c|X|,|V(G)|) for every X(?)V(G).In this paper,we prove the Woodall's conjecture:In bind (G)≥3/2,then G is pancyclic;andobtain some interesting results.     

On the homogenization of noncoercive variational problems

The paper deals with variational problems of the form $$\mathop {\inf }\limits_{u \in W^{1,p} (\Omega )} \int\limits_\Omega {a(\varepsilon ^{ - 1} x)(\left| {\nabla u} \right|^p + \left| {u - g} \right|^p )} dx,$$ where Ω is a bounded Lipschitzian domain in ? ^N , g∈L^p(Ω). The function a(x) is assumed to satisfy the following conditions:

1. a(x) is periodic and lower semicontinuous;
2. 0≤a(x)≤1 and the set {∈? ^N , a(x)>0} is connected in ? ^N Under these conditions, basic properties of homogenization (convergence of energies and generalized solutions) and properties of Г-convergence type are proved. Bibliography: 3 titles.

     

Neighborhood Union Conditions for Hamiltonicity of P 3-Dominated Graphs

As an extension of quasi claw-free graphs, the class of P ₃-dominated graphs has been introduced by Broersma and Vumar (Math Methods Oper Res 69:297–306, 2009). For a noncomplete graph G, the number NC and NC ₂ are defined as \({NC=\min\{|N(x)\cup N(y)|: x,y\in V(G) {\rm and} xy\notin E(G)\}\, {\rm and} NC_2=\min\{|N(x)\cup N(y)|: x,y\in V(G)\, {\rm and}\, d(x,y)=2 \}}\) , respectively. For a complete graph G, set \({NC=NC_{2}=|V(G)|-1}\) . In this paper, we prove that a 2-connected P ₃-dominated graph of order n is traceable if \({NC\geq (n-2)/2}\) . Moreover, we prove that a 3-connected P ₃-dominated graph of order n is hamiltonian if \({NC_2\geq (2n-6)/3}\) . Our results extend some previous results on claw-free graphs.     

Binding number and Hamiltonian(g, f)-factors in graphs

A(g, f)-factorF of a graphG is called a Hamiltonian(g, f)-factor ifF contains a Hamiltonian cycle. The binding number ofG is defined by $bind(G) = \min \left\{ {\frac{{|N_G (X)|}}{{|X|}}|\not 0 \ne X \subset V(G), N_G (X) \ne V(G)} \right\}$ . Let G be a connected graph, and let a andb be integers such that 4 ≤ a <b. Letg, f be positive integer-valued functions defined onV(G) such that a ≤g(x) < f(x) ≤ b for everyx ∈V(G). In this paper, it is proved that if $bind(G) \geqslant \frac{{(a + b - 5)(n - 1)}}{{(a - 2)n - 3(a + b - 5)}}, \nu (G) \geqslant \frac{{(a + b - 5)^2 }}{{a - 2}}$ and for any nonempty independent subset X ofV(G), thenG has a Hamiltonian(g, f)-factor.     

Characterizations of Strength Extremal Graphs

With graphs considered as natural models for many network design problems, edge connectivity κ′(G) and maximum number of edge-disjoint spanning trees τ(G) of a graph G have been used as measures for reliability and strength in communication networks modeled as graph G (see Cunningham, in J ACM 32:549–561, 1985; Matula, in Proceedings of 28th Symposium Foundations of Computer Science, pp 249–251, 1987, among others). Mader (Math Ann 191:21–28, 1971) and Matula (J Appl Math 22:459–480, 1972) introduced the maximum subgraph edge connectivity \({\overline{\kappa'}(G) = {\rm max} \{\kappa'(H) : H {\rm is} \, {\rm a} \, {\rm subgraph} \, {\rm of} G \}}\) . Motivated by their applications in network design and by the established inequalities $$\overline{\kappa'}(G) \ge \kappa'(G) \ge \tau(G),$$ we present the following in this paper:

1. For each integer k > 0, a characterization for graphs G with the property that \({\overline{\kappa'}(G) \le k}\) but for any edge e not in G, \({\overline{\kappa'}(G + e) \ge k+1}\) .
2. For any integer n > 0, a characterization for graphs G with |V(G)| = n such that κ′(G) = τ(G) with |E(G)| minimized.

     

Boolean approach to planar embeddings of a graph

The purpose of this paper which is a sequel of “ Boolean planarity characterization of graphs ” [9] is to show the following results.

1. Both of the problems of testing the planarity of graphs and embedding a planar graph into the plane are equivalent to finding a spanning tree in another graph whose order and size are bounded by a linear function of the order and the size of the original graph, respectively.
2. The number of topologically non-equivalent planar embeddings of a Hamiltonian planar graphG is τ(G)=2 ^c(H)?1, wherec (H) is the number of the components of the graphH which is related toG.

     

A generalization of the katona theorem for crosst-intersecting families

LetX be ann-element set and letA and? be families of subsets ofX. We say thatA and? are crosst-intersecting if |A ∩ B| ≥ t holds for all A ∈A and for allB ∈ ?. Suppose thatA and ? are crosst-intersecting. This paper first proves a crosst-intersecting version of Harper's Theorem:

1. There are two crosst-intersecting Hamming spheresA ₀,? ₀ with centerX such that |A| ≤ |A ₀| and|?| ≤ |? ₀| hold.
2. Suppose thatt ≥ 2 and that the pair of integers (|A) is maximal with respect to direct product ordering among pairs of crosst-intersecting families. Then,A and? are Hamming spheres with centerX.

Using these claims, the following conjecture of Frankl is proven:

1. Ifn + t = 2k ? 1 then |A| |?| ≤ max \(\left\{ {\left( {K_k^n + \left( {_{k - 1}^{n - 1} } \right)} \right)^2 ,K_k^n K_{k - 1}^n } \right\}\) holds, whereK _l ⁿ is defined as \(\left( {_n^n } \right)\left( {_{n - 1}^n } \right) + \cdots + \left( {_l^n } \right).\)
2. Ifn + t = 2k then |A| |? ≤ (K _k ⁿ )² holds.

The extremal configurations are also determined.     

On a permutablity problem for groups

Letm, n be positive integers. We denote byR(m, n) (respectivelyP(m, n)) the class of all groupsG such that, for everyn subsetsX ₁, X₂, . . .,X _n of sizem ofG there exits a non-identity permutation σ such that $X_1 X_2 ...X_n \cap X_{\sigma (1)} X_{\sigma (2)} ...X_{\sigma (n)} \ne \not 0$ (respectively X₁X₂ . . .X _n = X_σ(1)X{σ(2)} . . . X{gs(n)}). Let G be a non-abelian group. In this paper we prove that

1. G ∈ P(2,3) if and only ifG isomorphic to S₃, whereS _n is the symmetric group onn letters.
2. G ∈ R(2, 2) if and only if¦G¦ ≤ 8.
3. IfG is finite, thenG ∈ R(3, 2) if and only if¦G¦ ≤ 14 orG is isomorphic to one of the following: SmallGroup(16,i), i ∈ {3, 4, 6, 11, 12, 13}, SmallGroup(32,49), SmallGroup(32, 50), where SmallGroup(m, n) is the nth group of orderm in the GAP [13] library.

     

On the cyclicity and cocyclicity ofG-modules

LetG be a linear algebraic group over an algebraically closed fieldK. We call a (rational)G-module cyclic if it is generated by one element, and call it cocyclic if its dual is cyclic. We callG a c.c. group if the cyclicity is equivalent to the cocyclicity for anyG-module. IfG is not a c.c. group, the critical number ofG is the greatest integerc(G) such that the cyclicity is equivalent to the cocyclicity for anyG-module of dimension ≤c(G). In this paper we deduce some equivalent conditions for cyclicity and cocyclicity, and use them to prove the following main results:

1. A completely reducibleG is a c.c. group. The inverse holds for a connectedG in case charK>0, and also in case charK=0 with an exception thatG has a non-trivial unipotent quotient group.
2. \(\mathbb{G}_a \) is a c.c. group if charK=0; ( \(\mathbb{G}_a \) )=2 if charK>0.
3. IfG is reductive of typeA ₁ with charK=p>0, then $$c(G) = \left\{ \begin{gathered} \min \left\{ {2p - 1,p + 4} \right\}in case G is simply connected, \hfill \\ min\left\{ {2p - 1,p + 17} \right\}otherwise \hfill \\ \end{gathered} \right.$$

     

Neighborhood Unions and Z 3-Connectivity in Graphs

Let G be a 2-edge-connected simple graph on n ≥ 14 vertices, and let A be an abelian group with the identity element 0. If a graph G* is obtained by repeatedly contracting nontrivial A-connected subgraphs of G until no such a subgraph left, we say that G can be A-reduced to G*. In this paper, we prove that if for every ${uv\not\in E(G), |N(u) \cup N(v)| \geq \lceil \frac{2n}{3} \rceil}$ , then G is not Z ₃-connected if and only if G can be Z ₃-reduced to one of ${\{C_3,K_4,K_4^-, L\}}$ , where L is obtained from K ₄ by adding a new vertex which is joined to two vertices of K ₄.     

Indecomposable modules over right pure semisimple rings

The aim of this paper is to prove the following result. IfA is a right pure semisimple ring, then it satisfies one of the two following statements:

1. For any positive integern, there are at most finitely many indecomposable right modules of lengthn; or
2. There is an infinite number of integersd such that, for eachd, A has infinitely many indecomposable right modules of lengthd.

The result is derived with the aid of ultraproduct-technique.     

On a conjecture about automorphisms of finite p-groups

Let G be a nonabelian finite p-group. A longstanding conjecture asserts that G admits a noninner automorphism of order p. In this paper, we prove that if G satisfies one of the following conditions

1. ${\mathrm{rank}(G'\cap Z(G))\neq \mathrm{rank}(Z(G))}$
2. ${\frac{Z_{2}(G)}{Z(G)}}$ is cyclic
3. C _G (Z(Φ(G))) = Φ(G) and ${\frac{Z_{2}(G)\cap Z(\Phi(G))}{Z(G)} }$ is not elementary abelian of rank rs, where r = d(G) and s = rank (Z(G)),

then G has a noninner central automorphism of order p which fixes Φ(G) elementwise.     

Covering graphs by the minimum number of equivalence relations

An equivalence graph is a vertex disjoint union of complete graphs. For a graphG, let eq(G) be the minimum number of equivalence subgraphs ofG needed to cover all edges ofG. Similarly, let cc(G) be the minimum number of complete subgraphs ofG needed to cover all its edges. LetH be a graph onn vertices with maximal degree ≦d (and minimal degree ≧1), and letG= \(\bar H\) be its complement. We show that $$\log _2 n - \log _2 d \leqq eq(G) \leqq cc(G) \leqq 2e^2 (d + 1)^2 \log _e n.$$ The lower bound is proved by multilinear techniques (exterior algebra), and its assertion for the complement of ann-cycle settles a problem of Frankl. The upper bound is proved by probabilistic arguments, and it generalizes results of de Caen, Gregory and Pullman.     

Odd cycles and matrices with integrality properties

A cycle of a bipartite graphG(V⁺, V^?; E) is odd if its length is 2 (mod 4), even otherwise. An odd cycleC is node minimal if there is no odd cycleC′ of cardinality less than that ofC′ such that one of the following holds:C′ ∩V ⁺ ?C ∩V ⁺ orC′ ∩V ^? ?C ∩V ^?. In this paper we prove the following theorem for bipartite graphs: For a bipartite graphG, one of the following alternatives holds:

-All the cycles ofG are even.

-G has an odd chordless cycle.

-For every node minimal odd cycleC, there exist four nodes inC inducing a cycle of length four.

-An edge (u, v) ofG has the property that the removal ofu, v and their adjacent nodes disconnects the graphG.

To every (0, 1) matrixA we can associate a bipartite graphG(V⁺, V^?; E), whereV ⁺ andV ^? represent respectively the row set and the column set ofA and an edge (i,j) belongs toE if and only ifa _ij = 1. The above theorem, applied to the graphG(V⁺, V^?; E) can be used to show several properties of some classes of balanced and perfect matrices. In particular it implies a decomposition theorem for balanced matrices containing a node minimal odd cycleC, having the property that no four nodes ofC induce a cycle of length 4. The above theorem also yields a proof of the validity of the Strong Perfect Graph Conjecture for graphs that do not containK ₄?e as an induced subgraph.