GEODETIC GAMES FOR GRAPHS

ABSTRACT

Let S be a subset of the vertex set V(G) of a nontrivial connected graph G. The geodetic closure (S) of S is the set of all vertices on geodesics between two vertices in S. The first player A chooses a vertex v₁ of G. The second player B then picks v₂ ≠ v₁ and forms the geodetic closure (S₂) = ({v₁, v₂}). Now A selects v₃ ε V—S₂ and forms (S₃) = ({v₁, v₂, v₃}), etc. The player who first selects a vertex v_n such that (S_n) = V wins the achievement game, but loses the avoidance game. These geodetic achievement and avoidance games are solved for several families of graphs by determining which player is the winner.     

PRODUCTS OF CIRCULANT GRAPHS

ABSTRACT

Graph products of circulants are studied. It is shown that if G and H are circulants and gcd(v(G), v(H)) = 1, then every B-product of G and H is again a circulant. We prove that if m ≠ 2, then the generalised prism K₂ ^mxC_n is a circulant iff n is odd. A similar result is deduced for the conjunction. We also prove that C_p x C_q is a circulant iff p and q are relatively prime. We close by showing that the composition of two circulants is again a circulant and explicitly describe the resultant circulant's jump sequence in terms of the constituent circulants' jump sequences.     

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.     

关于奇算术图

本文讨论了$n$个$m$长圈有一个公共结点图$C^n_m$, $n$个$m$长圈与$t$长路有一个公共结点图$C^n_m\cdot P_t$, $n$个$m$阶完全图有一个公共结点图$K^n_m$和星形图的同胚图的奇算术性问题.给出了完全图,完全二部图和圈是奇算术的充要条件.     

TWO RESULTS ON GENERALIZED CHROMATIC NUMBERS

Abstract

The m'th chromatic number X_m(G) of a graph G is the least number of colours required to colour the vertices of G such that no m-clique of G is mono-coloured. For each k ≥ 2 and m ≥ 2 we determine for which r a graph G with m'th chromatic number k and clique number r exists. We also determine for which n a graph G exists with X_n (G + K) = X_m (G) = k.     

An implication basis for linear forms

The main results of this paper are a generalization of the results of S. Fajtlowicz and J. Mycielski on convex linear forms. We show that if V_n is the variety generated by all possible algebras , where R denotes the real numbers and , for some , then any basis for the set of all identities satisfied by V_n is infinite. But on the other hand, the identities satisfied by V_n are a consequence of gL and μ_n, where μ_n is the n-ary medial law and the inference rule gL is an implication patterned after the classical rigidity lemma of algebraic geometry. We also prove that the identities satisfied by are a consequence of gL and μ_n iff {p₁, ... , p_n} is algebraically independent. We then prove analagous results for algebras of arbitrary type τ and in the final section of this paper, we show that analagous results hold for Abelian group hyperidentities. This paper is dedicated to Walter Taylor. Received July 16, 2005; accepted in final form January 12, 2006. The research of both authors was supported by an operating grant ODP0008215 from NSERC.     

Smallest maximally nonhamiltonian graphs

A graphG ismaximally nonhamiltonian iffG is not hamiltonian butG + e is hamiltonian for each edgee inG ^c, i.e., any two non-adjacent vertices ofG are ends of a hamiltonian path. Bollobás posed the problem of finding the least number of edges,f(n), possible in a maximally nonhamiltonian graph of ordern. Results of Bondy show thatf(n) 3/2 n forn 7. We exhibit graphs of even ordern 36 for which the bound is attained. These graphs are the snarks,J _k, of Isaacs and mild variations of them. For oddn 55 we construct graphs from the graphsJ _k showing that in this case,f(n) = 3n + 1/2 or 3n + 3/2 and leave the determination of which is correct as an open problem. Finally we note that the graphsJ _k, k 7 are hypohamiltonian cubics with girth 6.     

Extensions of thep-adic fields generated by the roots of a single polynomial in two variables

One of the generalizations of the Hilbert's Irreducibility Theorem states that if F(X, Y) is irreducible in Q _p [X, Y] then, for almost every n N, F(n, Y) is irreducible in Q _p [Y]. Let E{p, d} be the set of all the extensions of Q _p of degree d. We shall prove that for each subset S E{p, d}there exist polynomials F(X, Y) such that the set of extensions of Q _p generated by the roots of F (n, Y)is exactly S. Moreover we shall prove that all the functions f are induced by polynomials F(X) Z[X].M. S. C. N. 11S05, (11S15).The author would like to thank Prof. Roberto Dvornicich for several useful conversations and advices.     

Packing an equilateral polygon in a thin strip

LetP _m denote an equilateral polygon ofm sides with each side having length 1 and we allow the sides to cross and vertex repetitions. We consider the following question. What is the smallest widtht _m of a horizontal strip in the Euclidean plane that contains aP _m ? This problem has its origins in Euclidean Ramsey theory. Whenm is even, it is easy to see thatt _m =0. For a polygon with an odd number of sides, we prove that $\begin{gathered} t_{2n + 1} = \frac{{\sqrt {2n + 1} }}{{n + 1}} for 2n + 1 \equiv 3(\bmod 4) and \hfill \\ t_{2n + 1} = \sqrt {\frac{{2n + 1}}{{n^2 + 2n}}} for 2n + 1 \equiv 1(\bmod 4) \hfill \\ \end{gathered} $ respectively. Applying the result to unit distance graphs, we prove the following: SupposeG is a unit-distance graph, i.e.G can be drawn on the planeR ² such that each edge ofG is a straight line segment of length 1. IfG has no odd circuits of length greater than or equal to 15, thenX(G) ≤ 6, whereX(G) is the chromatic number ofG.     

Entropy bounds for perfect matchings and Hamiltonian cycles

For a graph G = (V,E) and x: E → ℜ⁺ satisfying Σ _e∋υ x _e = 1 for each υ ∈ V, set h(x) = Σ _e x _e log(1/x _e ) (with log = log₂). We show that for any n-vertex G, random (not necessarily uniform) perfect matching f satisfying a mild technical condition, and x _e =Pr(e∈f),

On Witten’s type of zeta values attached to <Emphasis Type="Italic">SO</Emphasis>(5)

In this paper, we consider Wittens type of zeta value attached to SO(5) defined by for nonnegative integers p, q, r, s. We prove that this value can be expressed as a rational linear combination of products of Riemanns zeta values at positive integers when this is convergent and p + q + r + s is odd.Received: 27 January 2003     

Divisibility properties of certain recurrent sequences

Let g and m be two positive integers, and let F be a polynomial with integer coefficients. We show that the recurrent sequence x₀ = g, x_n = x _n−1 ⁿ + F(n), n = 1, 2, 3,…, is periodic modulo m. Then a special case, with F(z) = 1 and with m = p > 2 being a prime number, is considered. We show, for instance, that the sequence x₀ = 2, x_n = x _n−1 ⁿ + 1, n = 1, 2, 3, …, has infinitely many elements divisible by every prime number p which is less than or equal to 211 except for three prime numbers p = 23, 47, 167 that do not divide x_n. These recurrent sequences are related to the construction of transcendental numbers ζ for which the sequences [ζ^n!], n = 1, 2, 3, …, have some nice divisibility properties. Bibliography: 18 titles. Published in Zapiski Nauchnykh Seminarov POMI, Vol. 322, 2005, pp. 76–82.     

Van der waerden and ramsey type games

Let us consider the following 2-player game, calledvan der Waerden game. The players alternately pick previously unpicked integers of the interval {1, 2, ...,N}. The first player wins if he has selected all members of ann-term arithmetic progression. LetW*(n) be the least integerN so that the first player has a winning strategy. By theRamsey game on k-tuples we shall mean a 2-player game where the players alternately pick previously unpicked elements of the completek-uniform hypergraph ofN verticesK _N ^k , and the first player wins if he has selected allk-tuples of ann-set. LetR _k*(n) be the least integerN so that the first player has a winning strategy. We prove (W* (n))¹/n → 2,R ₂*(n)<(2+ε) ⁿ andR _k ^* n<2 ^nk / ^k! fork ≧3.     

On the mean square formula for the Riemann zeta-function on the critical line

Ifu _n denotes thenth zero of the function ,Ivi has shown thatu _n+1 –u _n u _n ^1/2 for alln andu _n+1 –u _n u _n ^1/2 (log u_n)^–5for infinitely manyn. We sharpen his lower estimate for the gapu _n+1 –u _n o the best possible, namely,u _n+1 –u _n u _n ^1/2 for infinitely manyn.The author wishes to thank Dr. Kai-Man Tsang for his continual guidance.     

P<Subscript>4k-1</Subscript>-factorization of complete bipartite graphs

Let K_m,n be a complete bipartite graph with two partite sets having m and n vertices, respectively. A P_v-factorization of K_m,n is a set of edge-disjoint P_v-factors of K_m,n which partition the set of edges of K_m,n. When v is an even number, Wang and Ushio gave a necessary and sufficient condition for the existence of P_v-factorization of K_m,n. When v is an odd number, Ushio in 1993 proposed a conjecture. However, up to now we only know that Ushio Conjecture is true for v = 3. In this paper we will show that Ushio Conjecture is true when v = 4k - 1. That is, we shall prove that a necessary and sufficient condition for the existence of a P_4k-1-factorization of K_m,n is (1) (2k - 1)m ⩽ 2kn, (2) (2k - 1)n ⩽ 2km, (3) m + n ≡ 0 (mod 4k - 1), (4) (4k - 1)mn/[2(2k - 1)(m + n)] is an integer.     

Spectral triangles of Schrödinger operators with complex potentials

Consider the Schrödinger operator with a complex-valued potential v of period Let and be the eigenvalues of L that are close to respectively, with periodic (for n even), antiperiodic (for n odd), and Dirichelet boundary conditions on [0,1], and let be the diameter of the spectral triangle with vertices We prove the following statement: If then v(x) is a Gevrey function, and moreover      

The number of strictly increasing mappings of fences

Let X and Y be fences of size n and m, respectively and n, m be either both even or both odd integers (i.e., |m-n| is an even integer). Let \(r = \left\lfloor {{{(n - 1)} \mathord{\left/ {\vphantom {{(n - 1)} 2}} \right. \kern-0em} 2}} \right\rfloor\) . If 1<n<-m then there are \(a_{n,m} = (m + 1)2^{n - 2} - 2(n - 1)(\begin{array}{*{20}c} {n - 2} \\ r \\ \end{array} )\) of strictly increasing mappings of X to Y. If 1<-m<-n<-2m and s=1/2(n?m) then there are a _n,m+b _n,m+c _n of such mappings, where $$\begin{gathered} b_{n,m} = 8\sum\limits_{i = 0}^{s - 2} {\left( {\begin{array}{*{20}c} {m + 2i + 1} \\ l \\ \end{array} } \right)4^{s - 2 - 1} } \hfill \\ {\text{ }}c_n = \left\{ \begin{gathered} \left( {\begin{array}{*{20}c} {n - 1} \\ {s - 1} \\ \end{array} } \right){\text{ if both }}n,m{\text{ are even;}} \hfill \\ {\text{ 0 if both }}n,m{\text{ are odd}}{\text{.}} \hfill \\ \end{gathered} \right. \hfill \\ \end{gathered} $$      

Birkhoff strata of the Grassmannian Gr<Superscript>(2)</Superscript>: Algebraic curves

We study algebraic varieties and curves arising in the Birkhoff strata of the Sato Grassmannian Gr ⁽²⁾ . We show that the big cell Σ ₀ contains the tower of families of the normal rational curves of all odd orders. The strata Σ _2n, n = 1, 2, 3,..., contain hyperelliptic curves of genus n and their coordinate rings. The strata Σ _2n+1 , n = 0, 1, 2, 3,..., contain (2m + 1, 2m + 3) plane curves for n = 2m, 2m − 1 (m ≥ 2) and also (3, 4) and (3, 5) curves in Σ ₃ and Σ ₅ . Curves in the strata Σ _2n+1 have zero genus.     

On completely multiplicative functions whose values are roots of unity

Summary We prove that if a complex valued completely multiplicative function F and a positive integer ℓ≦5 satisfy the condition F(N) = U_ℓ, where U_ℓ is the set of all ℓ-th roots of unity, then {F(n+1) F(n) ∣ nε N} = U_ℓ.     

Weighted Non-Trivial Multiply Intersecting Families

Let n and r be positive integers. Suppose that a family satisfies F₁∩···∩F_r ≠∅ for all F₁, . . .,F_r ∈ and . We prove that there exists ε=ε(r) >0 such that holds for 1/2≤w≤1/2+ε if r≥13.