Degree sum and connectivity conditions for dominating cycles

For a graph G, let σ_k(G) be the minimum degree sum of an independent set of k vertices. Ore showed that if G is a graph of order n?3 with σ₂(G)?n then G is hamiltonian. Let κ(G) be the connectivity of a graph G. Bauer, Broersma, Li and Veldman proved that if G is a 2-connected graph on n vertices with σ₃(G)?n+κ(G), then G is hamiltonian. On the other hand, Bondy showed that if G is a 2-connected graph on n vertices with σ₃(G)?n+2, then each longest cycle of G is a dominating cycle. In this paper, we prove that if G is a 3-connected graph on n vertices with σ₄(G)?n+κ(G)+3, then G contains a longest cycle which is a dominating cycle.     

Connected graphs with maximal Q-index: The one-dominating-vertex case

By the signless Laplacian of a (simple) graph G we mean the matrix Q(G)=D(G)+A(G), where A(G),D(G) denote respectively the adjacency matrix and the diagonal matrix of vertex degrees of G. For every pair of positive integers n,k, it is proved that if 3?k?n-3, then H_n,k, the graph obtained from the star K_1,n-1 by joining a vertex of degree 1 to k+1 other vertices of degree 1, is the unique connected graph that maximizes the largest signless Laplacian eigenvalue over all connected graphs with n vertices and n+k edges.     

Spanning 3-ended trees in k-connected K 1,4-free graphs

A tree with at most m leaves is called an m-ended tree.Kyaw proved that every connected K1,4-free graph withσ4(G)n-1 contains a spanning 3-ended tree.In this paper we obtain a result for k-connected K1,4-free graphs with k 2.Let G be a k-connected K1,4-free graph of order n with k 2.Ifσk+3(G)n+2k-2,then G contains a spanning 3-ended tree.     

On the Range of Possible Integrities of Graphs G(n, k)

We discuss the range of values for the integrity of a graphs G(n, k) where G(n, k) denotes a simple graph with n vertices and k edges. Let I _max(n, k) and I _min(n, k) be the maximal and minimal value for the integrity of all possible G(n, k) graphs and let the difference be D(n, k) = I _max(n, k) − I _min(n, k). In this paper we give some exact values and several lower bounds of D(n, k) for various values of n and k. For some special values of n and for s < n ^1/4 we construct examples of graphs G _n  = G _n (n, n + s) with a maximal integrity of I(G _n ) = I(C _n ) + s where C _n is the cycle with n vertices. We show that for k = n ²/6 the value of D(n, n ²/6) is at least \frac?6-13n{\frac{\sqrt{6}-1}{3}n} for large n.     

Disconnected Complements of Steinhaus graphs

In 1976 Molluzzo asked for the conditions on a generating string of a Steinhaus graph that would guarantee that its complement would be connected. In this paper we give conditions that guarantee that the complement is not connected and a recursion, for the number of such strings. We also find tight upper and lower bounds for this recursion by examining the recursion d_σ(2k) = d_σ(k)+d_σ(k−1) and d_σ(2k+1) = 2d_σ(k) + 1.     

Almost continuity on generalized topological spaces

For any unbounded sequence {n _k } of positive real numbers, there exists a permutation {n _σ(k)} such that the discrepancies of {n _σ(k) x} obey the law of the iterated logarithm exactly in the same way as the uniform i.i.d. sequence {U _k }.     

More coverings by rook domains

The set V_kⁿ of all n-tuples (x₁, x₂,…, x_n) with x_i?, $\text{Z}$_k is considered. The problem treated in this paper is determining σ(n, k), the minimum size of a set W ? V_kⁿ such that for each x in V_kⁿ, there is an element in W that differs from x in at most one coordinate. By using a new constructive method, it is shown that σ(n, p) ? (p ? t + 1)p^n?r, where p is a prime and $\text{n = 1 +}\text{t(p}{}^{\mathrm{r?1}}\text{? 1)}\text{(p ? 1)}$ for some integers t and r. The same method also gives σ(7, 3) ? 216. Another construction gives the inequality σ(n, kt) ? σ(n, k)t^n?1 which implies that σ(q + 1, qt) = q^q?1t^q when q is a prime power. By proving another inequality σ(np + 1, p) ? σ(n, p)p^n(p?1), σ(10, 3) ? 5 · 3⁶ and σ(16, 5) ? 13 · 5¹² are obtained.     

On an interpolation property of outerplanar graphs

Let D be an acyclic orientation of a graph G. An arc of D is said to be dependent if its reversal creates a directed cycle. Let d(D) denote the number of dependent arcs in D. Define d_min(G) (d_max(G)) to be the minimum (maximum) number of d(D) over all acyclic orientations D of G. We determine d_min(G) for an outerplanar graph G and prove that G has an acyclic orientation with exactly k dependent arcs if d_min(G)?k?d_max(G).     

Removable matchings and hamiltonian cycles

For a graph G, let σ₂(G) denote the minimum degree sum of two nonadjacent vertices (when G is complete, we let σ₂(G)=∞). In this paper, we show the following two results: (i) Let G be a graph of order n≥4k+3 with σ₂(G)≥n and let F be a matching of size k in G such that G−F is 2-connected. Then G−F is hamiltonian or G≅K₂+(K₂∪K_n−4) or ; (ii) Let G be a graph of order n≥16k+1 with σ₂(G)≥n and let F be a set of k edges of G such that G−F is hamiltonian. Then G−F is either pancyclic or bipartite. Examples show that first result is the best possible.     

Small cycles and 2-factor passing through any given vertices in graphs

The theory of vertex-disjoint cycles and 2-factor of graphs has important applications in computer science and network communication. For a graph G, let σ ₂(G):=min?{d(u)+d(v)|uv ? E(G),u≠v}. In the paper, the main results of this paper are as follows:

1. Let k≥2 be an integer and G be a graph of order n≥3k, if σ ₂(G)≥n+2k?2, then for any set of k distinct vertices v ₁,…,v _k , G has k vertex-disjoint cycles C ₁,C ₂,…,C _k of length at most four such that v _i ∈V(C _i ) for all 1≤i≤k.
2. Let k≥1 be an integer and G be a graph of order n≥3k, if σ ₂(G)≥n+2k?2, then for any set of k distinct vertices v ₁,…,v _k , G has k vertex-disjoint cycles C ₁,C ₂,…,C _k such that:
   1. v _i ∈V(C _i ) for all 1≤i≤k.
   2. V(C ₁)∪???∪V(C _k )=V(G), and
   3. |C _i |≤4, 1≤i≤k?1.

Moreover, the condition on σ ₂(G)≥n+2k?2 is sharp.     

On the lifting of elliptic cusp forms to cusp forms on quaternionic unitary groups

Let H be a definite quaternion algebra over Q with discriminant DH and R a maximal order of H. We denote by Gn a quaternionic unitary group and put Γn=Gn(Q)∩GL2n(R). Let Sκ(Γn) be the space of cusp forms of weight κ with respect to Γn on the quaternion half-space of degree n. We construct a lifting from primitive forms in Sk(SL₂(Z)) to Sk+2n−2(Γn) and a lifting from primitive forms in Sk(Γ₀(d)) to Sk+2(Γ₂), where d is a factor of DH. These liftings are generalizations of the Maass lifting investigated by Krieg.     

Weak regularity and consecutive topologizations and regularizations of pretopologies

L. Foged proved that a weakly regular topology on a countable set is regular. In terms of convergence theory, this means that the topological reflection Tξ of a regular pretopology ξ on a countable set is regular. It is proved that this still holds if ξ is a regular σ-compact pretopology. On the other hand, it is proved that for each n<ω there is a (regular) pretopology ρ (on a set of cardinality c) such that k(RT)ρ>n(RT)ρ for each k<n and n(RT)ρ is a Hausdorff compact topology, where R is the reflector to regular pretopologies. It is also shown that there exists a regular pretopology of Hausdorff RT-order ?ω₀. Moreover, all these pretopologies have the property that all the points except one are topological and regular.     

Strongly regular graphs and finite Ramsey theory

Some connections between strongly regular graphs and finite Ramsey theory are drawn. Let B_n denote the graph K₂+K?_n. If there exists a strongly regular graph with parameters (υ, k, λ, μ), then the Ramsey number r(B_λ+1, B_{υ?2k+μ ?1})?υ+1. We consider the implications of this inequality for both Ramsey theory and the theory of strongly regular graphs.     

Spectral radius of digraphs with given dichromatic number

Let D be a digraph with vertex set V(D). A partition of V(D) into k acyclic sets is called a k-coloring of D. The minimum integer k for which there exists a k-coloring of D is the dichromatic number χ(D) of the digraph D. Denote G_n,k the set of the digraphs of order n with the dichromatic number k≥2. In this note, we characterize the digraph which has the maximal spectral radius in G_n,k. Our result generalizes the result of [8] by Feng et al.     

Strong ergodicity of nonnegative matrix products

The sequence H_k, k? 1, of n×n nonnegative matrices is said to be asymptotically homogeneous (with respect to D) if, for some probability vector D, $\text{D′H}{}_{\mathrm{k}}\text{D′H}{}_{\mathrm{k}}\text{1→D′}$ as k→∞. Under a prior compactness assumption on the set {H_k}, asymptotic homogeneity is shown to be necessary and sufficient for strong ergodicity, as r→∞, of T_p,r=H_p+1H_p+2?H_p+r in a unified expository account for the two cases: (i) each T_p,r is primitive; (ii) each T_p,r is stochastic and regular. The first of these generalizes a known result [2]; and further generalizations are made.     

Linear transformations on matrices: the invariance of generalized permutation matrices—III

Let F be a field, F1 be its multiplicative group, and $\text{H}$ = {H:H is a subgroup of F1 and there do not exist a, b?F1 such that Ha+b?H}. Let D_n be the dihedral group of degree n, H be a nontrivial group in $\text{H}$, and τ_n(H) = {α = (α₁, α₂,…, α_n):α_i?H}. For σ?D_n and α?τ_n(H), let P(σ, α) be the matrix whose (i,j) entry is α_iδ_iσ(j) (i.e., a generalized permutation matrix), and

$\text{P(D}{}_{\mathrm{n}}\text{, H) = {P(σ, α):σ?D}{}_{\mathrm{n}}\text{, α?τ}{}_{\mathrm{n}}\text{(H)}}$

. Let M_n(F) be the vector space of all n×n matrices over F and $\text{T}$P(D_n, H) = {T:T is a linear transformation on M_n (F) to itself and T(P(D_n, H)) = P(D_n, H)}. In this paper we classify all T in $\text{T}$P(D_n, H) and determine the structure of the group $\text{T}$P(D_n, H) (Theorems 1 to 4). An expository version of the main results is given in Sec. 1, and an example is given at the end of the paper.     

Graphic sequences with a realization containing a generalized friendship graph

Gould, Jacobson and Lehel [R.J. Gould, M.S. Jacobson, J. Lehel, Potentially G-graphical degree sequences, in: Y. Alavi, et al. (Eds.), Combinatorics, Graph Theory and Algorithms, vol. I, New Issues Press, Kalamazoo, MI, 1999, pp. 451-460] considered a variation of the classical Turán-type extremal problems as follows: for any simple graph H, determine the smallest even integer σ(H,n) such that every n-term graphic sequence π=(d₁,d₂,…,d_n) with term sum σ(π)=d₁+d₂+?+d_n≥σ(H,n) has a realization G containing H as a subgraph. Let F_t,r,k denote the generalized friendship graph on kt−kr+r vertices, that is, the graph of k copies of K_t meeting in a common r set, where K_t is the complete graph on t vertices and 0≤r≤t. In this paper, we determine σ(F_t,r,k,n) for k≥2, t≥3, 1≤r≤t−2 and n sufficiently large.     

Type-B generalized triangulations and determinantal ideals

For n≥3, let Ω_n be the set of line segments between the vertices of a convex n-gon. For j≥2, a j-crossing is a set of j line segments pairwise intersecting in the relative interior of the n-gon. For k≥1, let Δ_n,k be the simplicial complex of (type-A) generalized triangulations, i.e. the simplicial complex of subsets of Ω_n not containing any (k+1)-crossing.The complex Δ_n,k has been the central object of many papers. Here we continue this work by considering the complex of type-B generalized triangulations. For this we identify line segments in Ω_2n which can be transformed into each other by a 180^°-rotation of the 2n-gon. Let F_n be the set Ω_2n after identification, then the complex D_n,k of type-B generalized triangulations is the simplicial complex of subsets of F_n not containing any (k+1)-crossing in the above sense. For k=1, we have that D_n,1 is the simplicial complex of type-B triangulations of the 2n-gon as defined in [R. Simion, A type-B associahedron, Adv. Appl. Math. 30 (2003) 2-25] and decomposes into a join of an (n−1)-simplex and the boundary of the n-dimensional cyclohedron. We demonstrate that D_n,k is a pure, k(n−k)−1+kn dimensional complex that decomposes into a kn−1-simplex and a k(n−k)−1 dimensional homology-sphere. For k=n−2 we show that this homology-sphere is in fact the boundary of a cyclic polytope. We provide a lower and an upper bound for the number of maximal faces of D_n,k.On the algebraical side we give a term order on the monomials in the variables X_ij,1≤i,j≤n, such that the corresponding initial ideal of the determinantal ideal generated by the (k+1) times (k+1) minors of the generic n×n matrix contains the Stanley-Reisner ideal of D_n,k. We show that the minors form a Gröbner-Basis whenever k∈{1,n−2,n−1} thereby proving the equality of both ideals and the unimodality of the h-vector of the determinantal ideal in these cases. We conjecture this result to be true for all values of k<n.     

Eulerian numbers,Newcomb's problem and representations of symmetric groups

Consider a set of n positive integers consisting of μ₁ 1's, μ₂ 2's,…, μ_rr's. If the integer in the ith place in an arrangement σ of this set is σ(i), and a non-rise in σ is defined as σ(i+1)?σ(i), a problem that suggests itself is the determination of the number of arrangements σ with k non-rises. When each μ_i is unity, the problem is that of finding the number A(n, k) of permutations of distinct integers 1, 2,…, n with k descents, a descent being defined as σ(i+1)<σ(i). The number A(n, k) is known as an Eulerian number. The problem of finding the number of arrangements with k non-rises of the more general set, when not all of μ_i are unity, has appeared in the literature as one part of a problem on dealing a pack of cards, this having been proposed by the American astronomer Simon Newcomb (1835–1909).Both the Eulerian numbers and Newcomb's problem have accumulated a substantial literature. The present paper considers these topics from an entirely new stand-point, that of representations of the symmetric group. This approach yields a well-known recurrence for the Eulerian numbers and a known formula for them in terms of Stirling numbers. It also gives the solutions of the Newcomb problem and some recurrences between these solutions, not all of which have been found earlier. A simple connection is found between Stirling numbers and the Kostka numbers of symmetric group representation theory. The Eulerian numbers can also be expressed in terms of the Kostka numbers.The idea which is novel in this treatment and recurs almost as a motif throughout the paper is that of a skew-hook. This occurs in the first place in a very natural way as a picture of the rises and non-rises of σ, with the nodes of the skew-hook labelled successively as σ(1), σ(2),…. As the paper develops, a new form of skew-hook associated with σ emerges. This does not in general depict the rises and non-rises of σ, and it is now the edges, not the nodes, which carry integer labels. A new type of combinatorial number, here called a ψ-function, arises from these edge-labelled skew-hooks. The ψ-functions are intimately related to the Eulerian numbers and the Newcomb solutions and may have further combinatorial applications. The skew-hook treatment casts fresh light on MacMahon's solution of the Newcomb problem and on his “new symmetric functions”, and, if σ(i)?σ(i+1)?s defines an s-descent in σ, on the enumeration of permutations with ks-descents.Also some characters of the symmetric group with interesting properties and recurrences arise in the course of the paper.     

A new result on Davenport constant

Let G be a finite abelian group of order n and Davenport constant D(G). Let S=⁰h(S)_∏g∈Ggvg(S)∈F(G) be a sequence with a maximal multiplicity h(S) attained by 0 and t=|S|?n+D(G)−1. Then 0∈k_∑(S) for every 1?k?t+1−D(G). This is a refinement of the fundamental result of Gao [W.D. Gao, A combinatorial problem on finite abelian groups, J. Number Theory 58 (1996) 100-103].