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.     

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.     

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.     

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].     

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.     

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.     

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.     

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.     

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.     

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.     

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 the stability index for weighted composition operators

Let ?>0. A continuous linear operator T:C(X)?C(Y) is said to ?-preserve disjointness if ‖(Tf)(Tg)‖_∞≤?, whenever f,g∈C(X) satisfy ‖f‖_∞=‖g‖_∞=1 and fg≡0. In this paper we continue our study of the minimal interval where the possible maximal distance from a norm one operator which ?-preserves disjointness to the set of weighted composition maps may lie. We provide sharp bounds for both the finite and the infinite case, which turn out to be completely different.     

A note on the generalized min-sum set cover problem

In this paper, we consider the generalized min-sum set cover problem, introduced by Azar, Gamzu, and Yin (STOC 2009). Bansal, Gupta, and Krishnaswamy (SODA 2010) give a 485-approximation algorithm for the problem. We are able to alter their algorithm and analysis to obtain a 28-approximation algorithm, improving the performance guarantee by an order of magnitude. We use concepts from α-point scheduling to obtain our improvements.     

Graph designs for the eight-edge five-vertex graphs

The existence of graph designs for the two nonisomorphic graphs on five vertices and eight edges is determined in the case of index one, with three possible exceptions in total. It is established that for the unique graph with vertex sequence (3, 3, 3, 3, 4), a graph design of order n exists exactly when and n≠16, with the possible exception of n=48. For the unique graph with vertex sequence (2,3,3,4,4), a graph design of order n exists exactly when , with the possible exceptions of n∈{32,48}.     

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 demand pooling anomaly in inventory theory

The demand pooling anomaly of inventory theory of type F amounts to a kind of restricted order relation between the individual demands (assumed to be independent) and their average. In this paper, we present some sufficient conditions for the type F anomaly not to occur for two i.i.d. demands; furthermore we provide an asymptotic result showing whether this anomaly occurs for large n for a class of distributions containing all distributions with finite mean.     

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.     

Maximally resonant polygonal systems

A benzenoid system G is k-resonant if any set F of no more than k disjoint hexagons is a resonant pattern, i.e, G−F has a perfect matching. In 1990’s M. Zheng constructed the 3-resonant benzenoid systems and showed that they are maximally resonant, that is, they are k-resonant for all k≥1. Recently, the equivalence of 3-resonance and maximal resonance has been shown to be valid also for coronoid systems, carbon nanotubes, polyhexes in tori and Klein bottles, and fullerene graphs. So our main problem is to investigate the extent of graphs possessing this interesting property. In this paper, by replacing the above hexagons with even faces, we define k-resonance of graphs in surfaces, possibly with boundary, in a unified way. Some exceptions exist. For plane polygonal systems tessellated with polygons of even size at least six such that all inner vertices have the same degree three and the others have degree two or three, we show that such 3-resonant polygonal systems are indeed maximally resonant. They can be constructed by gluing and lapping operations on three types of basic graphs.     

Endomorphisms of the shift dynamical system, discrete derivatives, and applications

All continuous endomorphisms f_∞ of the shift dynamical system S on the 2-adic integers Z₂ are induced by some , where n is a positive integer, B_n is the set of n-blocks over {0, 1}, and f_∞(x)=y₀y₁y₂… where for all i∈N, y_i=f(x_ix_i+1…x_i+n−1). Define D:Z₂→Z₂ to be the endomorphism of S induced by the map {(00,0),(01,1),(10,1),(11,0)} and V:Z₂→Z₂ by V(x)=−1−x. We prove that D, V°D, S, and V°S are conjugate to S and are the only continuous endomorphisms of S whose parity vector function is solenoidal. We investigate the properties of D as a dynamical system, and use D to construct a conjugacy from the 3x+1 function T:Z₂→Z₂ to a parity-neutral dynamical system. We also construct a conjugacy R from D to T. We apply these results to establish that, in order to prove the 3x+1 conjecture, it suffices to show that for any m∈Z⁺, there exists some n∈N such that R⁻¹(m) has binary representation of the form or .