Bilateral inversions and terminating basic hypergeometric series identities

The q-analogue of Legendre inversions is established and generalized to bilateral sequences. They are employed to investigate the dual relations of three basic formulae due to Jackson and Bailey, on balanced ₃?₂-series, well-poised ₈?₇-series and bilateral ₆ψ₆-series. Several terminating well-poised series identities are consequently derived, including the q-Dixon formulae on terminating ₃ψ₃-series and two terminating well-poised ₅ψ₅-series identities due to [F.H. Jackson, Certain q-identities, Quart. J. Math. (Oxford) 12 (1941) 167-172; W.N. Bailey, On the analogue of Dixon’s theorem for bilateral basic hypergeometric series, Quart. J. Math. (Oxford) 1 (1950) 318-320].     

On the spectral characterization of some unicyclic graphs

Let H(n;q,n₁,n₂) be a graph with n vertices containing a cycle C_q and two hanging paths P_n1 and P_n2 attached at the same vertex of the cycle. In this paper, we prove that except for the A-cospectral graphs H(12;6,1,5) and H(12;8,2,2), no two non-isomorphic graphs of the form H(n;q,n₁,n₂) are A-cospectral. It is proved that all graphs H(n;q,n₁,n₂) are determined by their L-spectra. And all graphs H(n;q,n₁,n₂) are proved to be determined by their Q-spectra, except for graphs with a being a positive even number and with b≥4 being an even number. Moreover, the Q-cospectral graphs with these two exceptions are given.     

Matching polynomials for chains of cycles

Došli? and Måløy (2010) [2] obtained the extremal 6-cactus chains with respect to the number of matchings and of independent sets. Motivated by the prior paper, in this paper we give recurrences for matching polynomials of ortho-chains and meta-chains, and show that they are the h-cactus chains with the most matchings.     

A construction of imprimitive symmetric graphs which are not multicovers of their quotients

Let Σ be a finite X-symmetric graph of valency , and s≥1 an integer. In this article we give a sufficient and necessary condition for the existence of a class of finite imprimitive (X,s)-arc-transitive graphs which have a quotient isomorphic to Σ and are not multicovers of that quotient, together with a combinatorial method, called the double-star graph construction, for constructing such graphs. Moreover, for any X-symmetric graph Γ admitting a nontrivial X-invariant partition B such that Γ is not a multicover of Γ_B, we show that there exists a sequence of -invariant partitions B=B₀,B₁,…,B_m of V(Γ), where m≥1 is an integer, such that B_i is a proper refinement of B_i−1, Γ_Bi is not a multicover of Γ_Bi−1 and Γ_Bi can be reconstructed from Γ_Bi−1 by the double-star graph construction, for i=1,2,…,m, and that either Γ≅Γ_Bm or Γ is a multicover of Γ_Bm.     

Applications of operator identities to the multiple q-binomial theorem and q-Gauss summation theorem

In this paper, we first give an interesting operator identity. Furthermore, using the q-exponential operator technique to the multiple q-binomial theorem and q-Gauss summation theorem, we obtain some transformation formulae and summation theorems of multiple basic hypergeometric series.     

Maximal independent sets in minimum colorings

Every graph G contains a minimum vertex-coloring with the property that at least one color class of the coloring is a maximal independent set (equivalently, a dominating set) in G. Among all such minimum vertex-colorings of the vertices of G, a coloring with the maximum number of color classes that are dominating sets in G is called a dominating-χ-coloring of G. The number of color classes that are dominating sets in a dominating-χ-coloring of G is defined to be the dominating-χ-color number of G. In this paper, we continue to investigate the dominating-χ-color number of a graph first defined and studied in [1].     

Set systems without a 3-simplex

A 3-simplex is a collection of four sets A₁,…,A₄ with empty intersection such that any three of them have nonempty intersection. We show that the maximum size of a set system on n elements without a 3-simplex is for all n≥1, with equality only achieved by the family of sets containing a given element or of size at most 2. This extends a result of Keevash and Mubayi, who showed the conclusion for n sufficiently large.     

A local prime factor decomposition algorithm

This work is concerned with the prime factor decomposition (PFD) of strong product graphs. A new quasi-linear time algorithm for the PFD with respect to the strong product for arbitrary, finite, connected, undirected graphs is derived.Moreover, since most graphs are prime although they can have a product-like structure, also known as approximate graph products, the practical application of the well-known “classical” prime factorization algorithm is strictly limited. This new PFD algorithm is based on a local approach that covers a graph by small factorizable subgraphs and then utilizes this information to derive the global factors. Therefore, we can take advantage of this approach and derive in addition a method for the recognition of approximate graph products.     

Duality theory and propagation rules for higher order nets

Higher order nets and sequences are used in quasi-Monte Carlo rules for the approximation of high dimensional integrals over the unit cube. Hence one wants to have higher order nets and sequences of high quality.In this paper we introduce a duality theory for higher order nets whose construction is not necessarily based on linear algebra over finite fields. We use this duality theory to prove propagation rules for such nets. This way we can obtain new higher order nets (sometimes with improved quality) from existing ones. We also extend our approach to the construction of higher order sequences.     

The order of hypotraceable oriented graphs

A digraph of order n is hypotraceable if it is nontraceable but all its induced subdigraphs of order n−1 are traceable. Grötschel et al. (1980) [M. Grötschel, C. Thomassen, Y. Wakabayashi, Hypotraceable digraphs, J. Graph Theory 4 (1980) 377–381] constructed an infinite family of hypotraceable oriented graphs, the smallest of which has order 13. We show that there exist hypotraceable oriented graphs of order n for every n≥8 except possibly for n=9,11 and that is the only one of order less than 8.Furthermore, we determine all the hypotraceable oriented graphs of order 8 and explain the relevance of these results to the problem of determining, for given k≥2, the maximum order of nontraceable oriented digraphs each of whose induced subdigraphs of order k is traceable.     

Large sets of resolvable idempotent Latin squares

An idempotent Latin square of order v is called resolvable and denoted by RILS(v) if the v(v−1) off-diagonal cells can be resolved into v−1 disjoint transversals. A large set of resolvable idempotent Latin squares of order v, briefly LRILS(v), is a collection of v−2 RILS(v)s pairwise agreeing on only the main diagonal. In this paper we display some recursive and direct constructions for LRILSs.     

Extremal infinite graph theory

We survey various aspects of infinite extremal graph theory and prove several new results. The lead role play the parameters connectivity and degree. This includes the end degree. Many open problems are suggested.     

On fractional integration formulae for Aleph functions

This paper is devoted to the study of a new special function, which is called, according to the symbol used to represent this function, as an Aleph function. This function is an extension of the I-function, which itself is a generalization of the well-known and familiar G- and H-functions in one variable. In this paper, a notation and complete definition of the Aleph function will be presented. Fractional integration of the Aleph functions, in which the argument of the Aleph function contains a factor t^λ(1 − t)^μ, λ, μ > 0, will be investigated. The results derived are of most general character and include many results given earlier by various authors including Kilbas [10], Kilbas and Saigo [11] and Galué [6] and others. The results obtained form the key formulae for the results on various potentially useful special functions of physical and biological sciences and technology available in the literature.     

On a Lovász-type lemma, applied to Brooks’ theorem for list-colouring

In this paper, I present a new structural lemma for k-regular graphs, similar to an earlier lemma by Lovász (1975) [5]. The new lemma is then used to give an algebraic proof of Brooks’ theorem for list-colouring.     

Minimum monopoly in regular and tree graphs

In this paper we consider a graph optimization problem called minimum monopoly problem, in which it is required to find a minimum cardinality set S⊆V, such that, for each u∈V, |N[u]∩S|?|N[u]|/2 in a given graph G=(V,E). We show that this optimization problem does not have a polynomial-time approximation scheme for k-regular graphs (k?5), unless P=NP. We show this by establishing two L-reductions (an approximation preserving reduction) from minimum dominating set problem for k-regular graphs to minimum monopoly problem for 2k-regular graphs and to minimum monopoly problem for (2k-1)-regular graphs, where k?3. We also show that, for tree graphs, a minimum monopoly set can be computed in linear time.     

On the complexity of the independent set problem in triangle graphs

We consider the complexity of the maximum (maximum weight) independent set problem within triangle graphs, i.e., graphs G satisfying the following triangle condition: for every maximal independent set I in G and every edge uv in G−I, there is a vertex w∈I such that {u,v,w} is a triangle in G. We also introduce a new graph parameter (the upper independent neighborhood number) and the corresponding upper independent neighborhood set problem. We show that for triangle graphs the new parameter is equal to the independence number. We prove that the problems under consideration are NP-complete, even for some restricted subclasses of triangle graphs, and provide several polynomially solvable cases for these problems within triangle graphs. Furthermore, we show that, for general triangle graphs, the maximum independent set problem and the upper independent neighborhood set problem cannot be polynomially approximated within any fixed constant factor greater than one unless P=NP.     

Improved algorithms for path partition and related problems

We study the L_∞ path partition problem: given a path of n weighted vertices and an integer k, remove k−1 edges from the path so that the maximum absolute deviation of the weights of the resulting k sub-paths from their mean is minimized. Previously, the best algorithm solves this problem in O(nklogk) time. We present an O(nk) time algorithm. We also give improved solutions for two related problems: the L_d path partition problem and the web proxies placement problem.     

Graph-like spaces: An introduction

Thomassen and Vella (Graph-like continua, augmenting arcs, and Menger’s Theorem, Combinatorica, doi:10.1007/s00493-008-2342-9) have recently introduced the notion of a graph-like space, simultaneously generalizing infinite graphs and many of the compact spaces recently used by Diestel or Richter (and their coauthors) to study cycle spaces and related problems in infinite graphs. This work is a survey to introduce graph-like spaces and shows how many of these works on compact spaces can be generalized to compact graph-like spaces.     

Elementary submodels in infinite combinatorics

The use of elementary submodels is a simple but powerful method to prove theorems, or to simplify proofs in infinite combinatorics. First we introduce all the necessary concepts of logic, then we prove classical theorems using elementary submodels. We also present a new proof of Nash-Williams’s theorem on cycle decomposition of graphs, and finally we improve a decomposition theorem of Laviolette concerning bond-faithful decompositions of graphs.     

Short proofs of summation and transformation formulas for basic hypergeometric series

We show that several terminating summation and transformation formulas for basic hypergeometric series can be proved in a straightforward way. Along the same line, new finite forms of Jacobi's triple product identity and Watson's quintuple product identity are also proved.