Connected signed graphs of fixed order,size, and number of negative edges with maximal index

In this paper we focus on connected signed graphs of fixed number of vertices, positive edges and negative edges that maximize the largest eigenvalue (also called the index) of their adjacency matrix. In the first step we determine these signed graphs in the set of signed generalized theta graphs. Concerning the general case, we use the eigenvector techniques for getting some structural properties of resulting signed graphs. In particular, we prove that positive edges induce nested split subgraphs, while negative edges induce double nested signed subgraphs. We observe that our concept can be applied when considering balancedness of signed graphs (the property that is extensively studied in both mathematical and non-mathematical context).     

On fixed subgroups of maximal rank

We show that, in the free group F of rank n, n is the maximal length of strictly ascending chains of maximal rank fixed subgroups, that is, rank n subgroups of the form Fix^{^} for some 4> L Aut(F). We further show that, in the rank two case, if the intersection of an arbitrary family of proper maximal rank fixed subgroups has rank two then all those subgroups are equal. In particular, every G < Aut(F) with r(FixG) = 2 is either trivial or infinite cyclic.     

On the number of maximal bipartite subgraphs of a graph

We show new lower and upper bounds on the maximum number of maximal induced bipartite subgraphs of graphs with n vertices. We present an infinite family of graphs having 105^n/10 ≈ 1.5926ⁿ; such subgraphs show an upper bound of O(12^n/4) = O(1.8613ⁿ) and give an algorithm that finds all maximal induced bipartite subgraphs in time within a polynomial factor of this bound. This algorithm is used in the construction of algorithms for checking k‐colorability of a graph. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 127–132, 2005     

On the number of hamiltonian cycles in a maximal planar graph

We consider the problem of the minimum number of Hamiltonian cycles that could be present in a Hamiltonian maximal planar graph on p vertices. In particular, we construct a p-vertex maximal planar graph containing exactly four Hamiltonian cycles for every p ≥ 12. We also prove that every 4-connected maximal planar graph on p vertices contains at least p/(log₂ p) Hamiltonian cycles.     

On the number of maximal sum-free sets

It is shown that the set contains at most maximal sum-free subsets, provided is large enough.

     

On the number of combinations without a fixed distance

An explicit formula is derived for the number of k-element subsets A of {1,2,…n} such that no two elements whose difference is q are in A.     

On the maximal number of solutions of a problem in linear inequalities

The problemy=Ax+c,x≧0,y≧0, (x, y)=0 is considered, where the square real matrixA and the real vectorc are the data and a solution is a pair of vectorsx, y. Under certain conditions on the matrixA there exists a solution for every vectorc, but it cannot be unique for everyc. We prove that under these conditions the maximal number of solutions is 2 ⁿ − 1.     

Galois group of the maximal ℓ-extension with a fixed ramification of the rational number field

The problem of the isomorphism of certain pro-p-groups is considered.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 91, pp. 169–170, 1979.The author dedicates this paper to A. I. Vinogradov on the occasion of his 50th birthday.     

On the number of groups of a given order

Letting G(n) denote the number of nonisomorphic groups of order n, it is shown that for square-free n, G(n) ≤ ?(n) and G(n) ≤ (log n)^c on a set of positive density. Letting F_k(x) denote the number of n ≤ x for which G(n) = k, it is shown that $\text{F}{}_2\text{(x) =}\text{O(x(}\text{log}{}_4\text{x)}\text{(}\text{log}{}_3\text{x)}{}^2\text{)}$, where log_rx denotes the r-fold iterated logarithm.     

Positive circuits and maximal number of fixed points in discrete dynamical systems

We consider a product X of n finite intervals of integers, a map F from X to itself, the asynchronous state transition graph Γ(F) on X that Thomas proposed as a model for the dynamics of a network of n genes, and the interaction graph G(F) that describes the topology of the system in terms of positive and negative interactions between its n components. Then, we establish an upper bound on the number of fixed points for F, and more generally on the number of attractors in Γ(F), which only depends on X and on the topology of the positive circuits of G(F). This result generalizes the following discrete version of Thomas’ conjecture recently proved by Richard and Comet: If G(F) has no positive circuit, then Γ(F) has a unique attractor. This result also generalizes a result on the maximal number of fixed points in Boolean networks obtained by Aracena, Demongeot and Goles. The interest of this work in the context of gene network modeling is briefly discussed.     

On the number of maximal subgroups of a finite solvable group

For a finite solvable group G and prime number p, we use elementary methods to obtain an upper bound for \mathfrak m_p(G){\mathfrak {m}_{p}(G)} , defined as the number of maximal subgroups of G whose index in G is a power of p. From this we derive an upper bound on the total number of maximal subgroups of a finite solvable group in terms of its order. This bound improves existing bounds, and we identify conditions on the order of a finite solvable group under which this bound is best possible.     

On the number of elements of given order in a finitep-group

A. Kulakoff [9] proved that forp>2 the numberN _k =N _k (G) of solutions of the equationx ^{p k} =e in a non-cyclicp-groupG is divisible byp ^k+1. This result is a generalization of the well-known theorem of G. A. Miller asserting that the numberC _k =C _k (G) of cyclic subgroups of orderp ^k >p>2 is divisible byp. In this note we show that, as a rule: (1) ifk>1, thenN _k ≡0(modp ^k+p ); (2) ifk>2, thenC _k ≡0(modp ^p ). These facts are generalizations of many results from [1–5,8,9].     

On the number of cycles of length 4 in a maximal planar graph

Let p and C₄ (G) be the number of vertices and the number of 4-cycles of a maximal planar graph G, respectively. Hakimi and Schmeichel characterized those graphs G for which C₄ (G) = 1/2(p² + 3p - 22). This characterization is correct if p ≥ 9. However, for p = 7 or 8, there is exactly one other graph which violates the theorem in the sense that the upper bound of C₄ (G) is also attained.     

On the number of cycles of length k in a maximal planar graph

Let G be a maximal planar graph with p vertices, and let C_k(G) denote the number of cycles of length k in G. We first present tight bounds for C₃(G) and C₄(G) in terms of p. We then give bounds for C_k(G) when 5 ≤ k ≤ p, and consider in particular bounds for C_p(G), in terms of p. Some conjectures and unsolved problems are stated.