Relation between frobenius and 2-frobenius groups with order components of finite groups

IfG is a finite group, we define its prime graph Г(G), as follows: its vertices are the primes dividing the order ofG and two verticesp, q are joined by an edge, if there is an element inG of orderpq. We denote the set of all the connected components of the graph Г(G) by T(G)= {π_i(G), fori = 1,2, …,t(G)}, where t(G) is the number of connected components of Г(G). We also denote by π(n) the set of all primes dividingn, wheren is a natural number. Then ¦G¦ can be expressed as a product of m₁, m₂, …, m_t(G), where m_i’s are positive integers with π(m_i) = π_i. Thesem _i ’s are called the order components ofG. LetOC(G) := {m ₁,m ₂, …,m _t (G)} be the set of order components ofG. In this paper we prove that, if G is a finite group andOC(G) =OC(M), where M is a finite simple group witht(M) ≥ 2, thenG is neither Frobenius nor 2-Frobenius.     

Optimal labelling of a product of two paths

If G is a graph with p vertices and at least one edge, we set φ (G) = m n max |f(u) ? f(v)|, where the maximum is taken over all edges uv and the minimum over all one-to-one mappings f : V(G) → {1, 2, …, p}: V(G) denotes the set of vertices of G.P_n will denote a path of length n whose vertices are integers 1, 2, …, n with i adjacent to j if and only if |i ? j| = 1. P_m × P_n will denote a graph whose vertices are elements of {1, 2, …, m} × {1, 2, …, n} and in which (i, j), (r, s) are adjacent whenever either i = r and |j ? s| = 1 or j = s and |i ? r| = 1.Theorem.If max(m, n) ? 2, thenφ(P_m × P_n) = min(m, n).     

Some results on starlike trees and sunlike graphs

A tree is called starlike if it has exactly one vertex of degree greater than two. In [4] it was proved that two starlike treesG andH are cospectral if and only if they are isomorphic. We prove here that there exist no two non-isomorphic Laplacian cospectral starlike trees. Further, letG be a simple graph of ordern with vertex setV(G)={1,2, …,n} and letH={H ₁,H ₂, ...H _n } be a family of rooted graphs. According to [2], the rooted productG(H) is the graph obtained by identifying the root ofH _i with thei-th vertex ofG. In particular, ifH is the family of the paths $P_{k_1 } , P_{k_2 } , ..., P_{k_n } $ with the rooted vertices of degree one, in this paper the corresponding graphG(H) is called the sunlike graph and is denoted byG(k ₁,k ₂, …,k _n ). For any (x ₁,x ₂, …,x _n ) ∈I _* ⁿ , whereI _*={0,1}, letG(x ₁,x ₂, …,x _n ) be the subgraph ofG which is obtained by deleting the verticesi ₁, i₂, …,i _j ∈ V(G) (0≤j≤n), provided that $x_{i_1 } = x_{i_2 } = ... = x_{i_j } = 0$ . LetG(x ₁,x ₂,…, x _n] be the characteristic polynomial ofG(x ₁,x ₂,…, x _n ), understanding thatG[0, 0, …, 0] ≡ 1. We prove that $$G[k_1 , k_2 ,..., k_n ] = \Sigma _{x \in ^{I_ * ^n } } \left[ {\Pi _{i = 1}^n P_{k_i + x_i - 2} (\lambda )} \right]( - 1)^{n - (\mathop \Sigma \limits_{i = 1}^n x_i )} G[x_1 , x_2 , ..., x_n ]$$ where x=(x ₁,x ₂,…,x _n );G[k ₁,k ₂,…,k _n ] andP _n (γ) denote the characteristic polynomial ofG(k ₁,k ₂,…,k _n ) andP _n , respectively. Besides, ifG is a graph with λ₁(G)≥1 we show that λ₁(G)≤λ₁(G(k ₁,k ₂, ...,k _n )) < for all positive integersk ₁,k ₂,…,k _n , where λ₁ denotes the largest eigenvalue.     

Multiplicative infinite loop space theory

Let G be a finitely presented group given by its pre-abelian presentation <X1,…,Xm; Xe11ζ1,…,Xemmζ,ζm+1,…>, where ei≥0 for i = 1,…, m and ζj?G′ for j≥1. Let N be the subgroup of G generated by the normal subgroups [xeii, G] for i = 1,…, m. Then Dn+2(G)≡γn+2(G) (modNG′) for all n≥0, where G” is the second commutator subgroup of G,γn+2(G) is the (n+2)th term of the lower central series of G and Dn+2(G) = G∩(1+△n+2(G)) is the (n+2)th dimension subgroup of G.     

Solution of generalized bisymmetry type equations without surjectivity assumptions

Summary. The solution of the rectangular m ×n m \times n generalized bisymmetry equation¶¶F(G₁(x₁₁,...,x_1n),..., G_m(x_m1,...,x_mn))     =     G(F₁(x₁₁,..., x_m1),...,  F_n(x_1n,...,x_mn) ) F\bigl(G_1(x_{11},\dots,x_{1n}),\dots,\ G_m(x_{m1},\dots,x_{mn})\bigr) \quad = \quad G\bigl(F_1(x_{11},\dots, x_{m1}),\dots, \ F_n(x_{1n},\dots,x_{mn}) \bigr) (A)¶is presented assuming that the functions F, G_j, G and F_i (j = 1, ... , m , i = 1, ... , n , m S 2, n S 2) are real valued and defined on the Cartesian product of real intervals, and they are continuous and strictly monotonic in each real variable. Equation (A) is reduced to some special bisymmetry type equations by using induction methods. No surjectivity assumptions are made.     

Some Ramsey numbers for directed graphs

Given k directed graphs G₁,…,G_k the Ramsey number R(G₁,…, G_k) is the smallest integer n such that for any partition (U₁,…,U_k) of the arcs of the complete symmetric directed graph K_n, there exists an integer i such that the partial graph generated by U₁ contains G₁ as a subgraph. In the article we give a necessary and sufficient condition for the existence of Ramsey numbers, and, when they exist an upper bound function. We also give exact values for some classes of graphs. Our main result is: $\text{R(}\text{P}{}_{\mathrm{n}}\text{,….}\text{P}{}_{\mathrm{nk-1}}\text{, G) = n}{}_1\text{…n}{}_{\mathrm{k-1}}\text{(p-1) + 1}$, where G is a hamltonian directed graph with p vertices and $\text{P}{}_{\mathrm{n}}{}_{\mathrm{i}}$ denotes the directed path of length n_t     

On Ramsey numbers involving starlike multipartite graphs

The Ramsey number r(G, H) is evaluated exactly in certain cases in which both G and H are complete multipartite graphs K(n,₁, n₂, …. n_k). Specifically, each of the following cases is handled whenever n is sufficiently large: r(K(1, m₁, …. m_k), K(1, n)), r(K(1, m), K(n₁, …. n_k, n)), provided m ≧ 4, and r(K(1, 1, m), K(n_k, …, n_k, n)).     

On graphsG for which all large trees areG-good

LetG be a graph satisfying x(G) = k. The following problem is considered: WhichG have the property that, if n is large enough, the Ramsey numberr(G, T) has the value (k — 1)(n — 1) + 1 for all treesT onn vertices? It is shown thatG has this property if and only if for somem, G is a subgraph of bothL _k,m andM _K.m , whereL _k,m andM _k,m are two particulark-chromatic graphs. Indeed, it is shown thatr(L _k,m ,M _k,m ,T _n ) = (k — 1)(n — 1) + 1 whenn is large.     

A class of antimagic join graphs

A labeling f of a graph G is a bijection from its edge set E(G) to the set {1, 2, . . . , |E(G)|}, which is antimagic if for any distinct vertices x and y, the sum of the labels on edges incident to x is different from the sum of the labels on edges incident to y. A graph G is antimagic if G has an f which is antimagic. Hartsfield and Ringel conjectured in 1990 that every connected graph other than K 2 is antimagic. In this paper, we show that if G 1 is an n-vertex graph with minimum degree at least r, and G 2 is an m-vertex graph with maximum degree at most 2r-1 (m ≥ n), then G1 ∨ G2 is antimagic.     

GENERALISED MAXIMAL INDEPENDENCE AND CLIQUE NUMBERS OF GRAPHS

Abstract

A set B of vertices of a graph G = (V,E) is a k-maximal independent set (kMIS) if B is independent but for all ?-subsets X of B, where ? ? k—1, and all (? + 1)-subsets Y of V—B, the set (B—X) u Y is dependent. A set S of vertices of C is a k-maximal clique (kMc) of G iff S is a kMIS of [Gbar]. Let β_k, (G) (w_k(G) respectively) denote the smallest cardinality of a kMIS (kMC) of G—obviously β_k(G) = w_k([Gbar]). For the sequence m₁ ? m₂ ?…? m_n = r of positive integers, necessary and sufficient conditions are found for a graph G to exist such that w_k(G) = m_k for k = 1,2,…,n and w(G) = r (equivalently, β_k(G) = m_k for k = 1,2,…,n and β(G) = r). Define s_k(?,m) to be the largest integer such that for every graph G with at most s_k(?,m) vertices, β_k(G) ? ? or w_k(G) ? m. Exact values for s_k(?,m) if k ≥ 2 and upper and lower bounds for s₁(?,m) are de termined.     

Orientations of circle graphs

Let C(v₁, …,v_n) be a system consisting of a circle C with chords v₁, …,v_n on it having different endpoints. Define a graph G having vertex set V(G) = {v₁, …,v_n} and for which vertices v_i and v_j are adjacent in G if the chords v_i and v_j intersect. Such a graph will be called a circle graph. The chords divide the interior of C into a number of regions. We give a method which associates to each such region an orientation of the edges of G. For a given C(v₁, …,v_n) the number m of different orientations corresponding to it satisfies q + 1 ≤ m ≤ n + q + 1, where q is the number of edges in G. An oriented graph obtained from a diagram C(v₁, …,v_n) as above is called an oriented circle graph (OCG). We show that transitive orientations of permutation graphs are OCGs, and give a characterization of tournaments which are OCGs. When the region is a peripheral one, the orientation of G is acyclic. In this case we define a special orientation of the complement of G, and use this to develop an improved algorithm for finding a maximum independent set in G.     

A new neighborhood union condition for Hamiltonian graphs

For a vertex set {u ₁,u ₂,...,u _k} of a graphG withn vertices, let $$\begin{gathered} s(G;\{ u_1 ,u_2 ,...,u_k \} ) = \sum {1 \leqslant i< j \leqslant k\left| {N(u_i ) \cup N(u_j )} \right|,} \hfill \\ NC_k = \min \{ s(G;\{ x_1 ,...,x_k \} )\} :\{ x_1 ,...,x_k \} is an independent set\} . \hfill \\ \end{gathered} $$ In this paper, we shall prove that ifG is 3-connected andNC ₄≥3n, thenG is either a hamiltonian or Petersen graph. This generalizes some results on the neighborhood union conditions for hamiltonian graphs.     

On cyclic decompositions of the complete graph into the 2-regular graphs

The symbol C(m₁ ⁿ ₁m₂ ⁿ ₂...m_s ⁿ _s) denotes a 2-regular graph consisting ofn _i cycles of lengthm _i , i=1, 2,…,s. In this paper, we give some construction methods of cyclic(K _v ,G)-designs, and prove that there exists a cyclic(K _v , G)-design whenG=C((4m ₁) ⁿ ₁(4m ₂) ⁿ ₂...(4m _s ) ⁿ _s andv ≡ 1 (mod 2¦G¦).     

Partitioning complete multipartite graphs by monochromatic trees

The tree partition number of an r‐edge‐colored graph G, denoted by t_r(G), is the minimum number k such that whenever the edges of G are colored with r colors, the vertices of G can be covered by at most k vertex‐disjoint monochromatic trees. We determine t₂(K(n₁, n₂,…, n_k)) of the complete k‐partite graph K(n₁, n₂,…, n_k). In particular, we prove that t₂(K(n, m)) = ? (m‐2)/2ⁿ? + 2, where 1 ≤ n ≤ m. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 133–141, 2005     

Matchings in starlike trees

Let m(G,k) be the number of k-matchings in the graph G. We write G₁ ⪯ G₂ if m(G₁, k) ≤ m(G₂, k) for all k = 1, 2,…. A tree is said to be starlike if it possesses exactly one vertex of degree greater than two. The relation T₁ ⪯ T₂ is shown to hold for various pairs of starlike trees T₁, T₂. The starlike trees (with a given number of vertices), extremal with respect to the relation ⪯, are characterized.     

Prime interchange graphs of classes of matrices of zeros and ones

Let R = (r₁,…, r_m) and S = (s₁,…, s_n) be nonnegative integral vectors, and let $\text{U}$(R, S) denote the class of all m × n matrices of 0's and 1's having row sum vector R and column sum vector S. An invariant position of $\text{U}$(R, S) is a position whose entry is the same for all matrices in $\text{U}$(R, S). The interchange graph G(R, S) is the graph where the vertices are the matrices in $\text{U}$(R, S) and where two matrices are joined by an edge provided they differ by an interchange. We prove that when 1 ≤ r_i ≤ n ? 1 (i = 1,…, m) and 1 ≤ s_j ≤ m ? 1 (j = 1,…, n), G(R, S) is prime if and only if $\text{U}$(R, S) has no invariant positions.     

On the odd harmonious graphs with applications

The necessary conditions for the existence of odd harmonious labelling of graph are obtained. A cycle C _n is odd harmonious if and only if n≡0 (mod 4). A complete graph K _n is odd harmonious if and only if n=2. A complete k-partite graph K(n ₁,n ₂,…,n _k ) is odd harmonious if and only if k=2. A windmill graph K _n ^t is odd harmonious if and only if n=2. The construction ways of odd harmonious graph are given. We prove that the graph ∨ _i=1 ⁿ G _i , the graph G(+r ₁,+r ₂,…,+r _p ), the graph $\bar{K_{m}}+_{0}P_{n}+_{e}\bar{K_{t}}$ , the graph G∪(X+∪ _k=1 ⁿ Y _k ), some trees and the product graph P _m ×P _n etc. are odd harmonious. The odd harmoniousness of graph can be used to solve undetermined equation.     

Sparse Graphs which Decompose into Closed Trails of Arbitrary Lengths

A simple, connected even graph G with vertex set V(G) and edge set E(G) is said to be ADCT (Arbitrarily Decomposable into Closed Trails) if for any collection of positive integers x ₁, x ₂,...,x _m with and x _i ≥ 3 for 1 ≤ i ≤ m, there exists a decomposition of G into closed trails (circuits) of lengths x ₁, x ₂,...,x _m . In this note we construct an 8-regular ADCT graph on 6n vertices, for each each n ≥ 3. On the other hand, we also show that there are only finitely many 4-regular graphs which are ADCT. Received July 26, 2006. Final version received: March 5, 2008.     

Diameters of iterated clique graphs of chordal graphs

The clique graph K(G) of a graph is the intersection graph of maximal cliques of G. The iterated clique graph Kⁿ(G) is inductively defined as K(K^n?1(G)) and K¹(G) = K(G). Let the diameter diam(G) be the greatest distance between all pairs of vertices of G. We show that diam(Kⁿ(G)) = diam(G) — n if G is a connected chordal graph and n ≤ diam(G). This generalizes a similar result for time graphs by Bruce Hedman.     

Star partitions of graphs

Let G be a graph and n ≥ 2 an integer. We prove that the following are equivalent: (i) there is a partition (V₁,…,V_m) of V (G) such that each V_i induces one of stars K_1,1,…,K_1,n, and (ii) for every subset S of V(G), G\ S has at most n|S| components with the property that each of their blocks is an odd order complete graph. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 185–190, 1997