Coloring, location and domination of corona graphs

A vertex coloring of a graph G is an assignment of colors to the vertices of G so that every two adjacent vertices of G have different colors. A coloring related property of a graphs is also an assignment of colors or labels to the vertices of a graph, in which the process of labeling is done according to an extra condition. A set S of vertices of a graph G is a dominating set in G if every vertex outside of S is adjacent to at least one vertex belonging to S. A domination parameter of G is related to those structures of a graph that satisfy some domination property together with other conditions on the vertices of G. In this article we study several mathematical properties related to coloring, domination and location of corona graphs. We investigate the distance-k colorings of corona graphs. Particularly, we obtain tight bounds for the distance-2 chromatic number and distance-3 chromatic number of corona graphs, through some relationships between the distance-k chromatic number of corona graphs and the distance-k chromatic number of its factors. Moreover, we give the exact value of the distance-k chromatic number of the corona of a path and an arbitrary graph. On the other hand, we obtain bounds for the Roman dominating number and the locating–domination number of corona graphs. We give closed formulaes for the k-domination number, the distance-k domination number, the independence domination number, the domatic number and the idomatic number of corona graphs.     

Independence,irredundance, degrees and chromatic number in graphs

Let β(G) and IR(G) denote the independence number and the upper irredundance number of a graph G. We prove that in any graph of order n, minimum degree δ and maximum degree Δ≠0, IR(G)⩽n/(1+δ/Δ) and IR(G)−β(G)⩽((Δ−2)/2Δ)n. The two bounds are attained by arbitrarily large graphs. The second one proves a conjecture by Rautenbach related to the case Δ=3. When the chromatic number χ of G is less than Δ, it can be improved to IR(G)−β(G)⩽((χ−2)/2χ)n in any non-empty graph of order n⩾2.     

On lines, joints, and incidences in three dimensions

We extend (and somewhat simplify) the algebraic proof technique of Guth and Katz (2010) [9], to obtain several sharp bounds on the number of incidences between lines and points in three dimensions. Specifically, we show: (i) The maximum possible number of incidences between n lines in R³ and m of their joints (points incident to at least three non-coplanar lines) is Θ(m1/3n) for m?n, and Θ(m2/3n2/3+m+n) for m?n. (ii) In particular, the number of such incidences cannot exceed O(n3/2). (iii) The bound in (i) also holds for incidences between n lines and m arbitrary points (not necessarily joints), provided that no plane contains more than O(n) points and each point is incident to at least three lines. As a preliminary step, we give a simpler proof of (an extension of) the bound O(n3/2), established by Guth and Katz, on the number of joints in a set of n lines in R³. We also present some further extensions of these bounds, and give a trivial proof of Bourgain's conjecture on incidences between points and lines in 3-space, which is an immediate consequence of our incidence bounds, and which constitutes a much simpler alternative to the proof of Guth and Katz (2010) [9].     

A class of vertex-transitive digraphs,II

(1). We determine the number of non-isomorphic classes of self-complementary circulant digraphs with pq vertices, where p and q are distinct primes. The non-isomorphic classes of these circulant digraphs with pq vertices are enumerated. (2). We also determine the number of non-isomorphic classes of self-complementary, vertex-transitive digraphs with a prime number p vertices, and the number of self-complementary strongly vertex-transitive digraphs with p vertices. The non-isomorphic classes of strongly vertex-transitive digraphs with p vertices are also enumerated.     

Characterizing geometric designs, II

We provide a characterization of the classical point-line designs PG₁(n,q), where n?3, among all non-symmetric 2-(v,k,1)-designs as those with the maximal number of hyperplanes. As an application of this result, we characterize the classical quasi-symmetric designs PGn−2(n,q), where n?4, among all (not necessarily quasi-symmetric) designs with the same parameters as those having line size q+1 and all intersection numbers at least qn−4+?+q+1. Finally, we also give an explicit lower bound for the number of non-isomorphic designs having the same parameters as PG₁(n,q); in particular, we obtain a new proof for the known fact that this number grows exponentially for any fixed value of q.     

On the packing chromatic number of Cartesian products, hexagonal lattice, and trees

The packing chromatic number χ_ρ(G) of a graph G is the smallest integer k such that the vertex set of G can be partitioned into packings with pairwise different widths. Several lower and upper bounds are obtained for the packing chromatic number of Cartesian products of graphs. It is proved that the packing chromatic number of the infinite hexagonal lattice lies between 6 and 8. Optimal lower and upper bounds are proved for subdivision graphs. Trees are also considered and monotone colorings are introduced.     

Heisenberg characters, unitriangular groups, and Fibonacci numbers

Let Un(Fq) denote the group of unipotent n×n upper triangular matrices over a finite field with q elements. We show that the Heisenberg characters of Un+1(Fq) are indexed by lattice paths from the origin to the line x+y=n using the steps (1,0), (1,1), (0,1), (0,2), which are labeled in a certain way by nonzero elements of Fq. In particular, we prove for n?1 that the number of Heisenberg characters of Un+1(Fq) is a polynomial in q−1 with nonnegative integer coefficients and degree n, whose leading coefficient is the nth Fibonacci number. Similarly, we find that the number of Heisenberg supercharacters of Un(Fq) is a polynomial in q−1 whose coefficients are Delannoy numbers and whose values give a q-analogue for the Pell numbers. By counting the fixed points of the action of a certain group of linear characters, we prove that the numbers of supercharacters, irreducible supercharacters, Heisenberg supercharacters, and Heisenberg characters of the subgroup of Un(Fq) consisting of matrices whose superdiagonal entries sum to zero are likewise all polynomials in q−1 with nonnegative integer coefficients.     

Orthogonal F-rectangles,orthogonal arrays,and codes

The relationships between a set of orthogonal F-squares or F-rectangles and orthogonal arrays are described. The relationship between orthogonal arrays and error-correcting codes is demonstrated. The development of complete sets of orthogonal F-rectangles allows construction of codes of any word length and for any number of words. Likewise, the development of F-rectangle theory makes code construction much more flexible in terms of a variable number of symbols. The relationship among sets of orthogonal hyperrectangles, orthogonal arrays, and codes is also described.     

Random sieves,II

A proof is presented that the random sieve, a stochastic analogue of the sieve of Eratosthenes, generates sequences of numbers approximating the density of primes. The expected number E_n[h] of such numbers less than n satisfies

$\text{E}{}_{\mathrm{n}}\text{[h]/π(n)→1}$

and the actual number h(n), on any trial, approximates π(n) in the sense of the weak law of large numbers. Some additional results are given.     

Class numbers of algebraic number fields of Eisenstein type,II

Let K be an algebraic number field, of degree n, with a completely ramifying prime p, and let t be a common divisor of n and $\text{(p ? 1)}\text{2}$. Then it is proved that if K does not contain the unique subfield, of degree t, of the p-th cyclotomic number field, then we have (h_K, n) > 1, where h_K is the class number of K. As applications, we give several results on h_K of such algebraic number fields K.     

Circumference, chromatic number and online coloring

Erd?s conjectured that if G is a triangle free graph of chromatic number at least k≥3, then it contains an odd cycle of length at least k ^2?o(1) [13,15]. Nothing better than a linear bound ([3], Problem 5.1.55 in [16]) was so far known. We make progress on this conjecture by showing that G contains an odd cycle of length at least Ω(k log logk). Erd?s’ conjecture is known to hold for graphs with girth at least five. We show that if a graph with girth four is C ₅ free, then Erd?s’ conjecture holds. When the number of vertices is not too large we can prove better bounds on χ. We also give bounds on the chromatic number of graphs with at most r cycles of length 1 mod k, or at most s cycles of length 2 mod k, or no cycles of length 3 mod k. Our techniques essentially consist of using a depth first search tree to decompose the graph into ordered paths, which are then fed to an online coloring algorithm. Using this technique we give simple proofs of some old results, and also obtain several other results. We also obtain a lower bound on the number of colors which an online coloring algorithm needs to use to color triangle free graphs.     

Caps in PG(n,q),q even,n⩾3

Letm′₂(3,q) be the largest value ofk(k<q ²+1) for which there exists a completek-cap in PG(3,q),q even. In this paper, the known upper bound onm′₂(3,q) is improved. We also describe a number of intervals, fork, for which there does not exist a completek-cap in PG(3,q),q even. These results are then used to improve the known upper bounds on the number of points of a cap in PG(n, q),q even,n?4.     

Relations between Clar structures, Clar covers, and the sextet-rotation tree of a hexagonal system

Sextet rotations of the perfect matchings of a hexagonal system H are represented by the sextet-rotation-tree R(H), a directed tree with one root. In this article we find a one-to-one correspondence between the non-leaves of R(H) and the Clar covers of H, without alternating hexagons. Accordingly, the number (nl) of non-leaves of R(H) is not less than the number (cs) of Clar structures of H. We obtain some simple necessary and sufficient conditions, and a criterion for cs=nl, that are useful for the calculation of Clar polynomials. A procedure for constructing hexagonal systems with cs<nl is provided in terms of normal additions of hexagons.     

Graphs, partitions and Fibonacci numbers

The Fibonacci number of a graph is the number of independent vertex subsets. In this paper, we investigate trees with large Fibonacci number. In particular, we show that all trees with n edges and Fibonacci number >2^n-1+5 have diameter ?4 and determine the order of these trees with respect to their Fibonacci numbers. Furthermore, it is shown that the average Fibonacci number of a star-like tree (i.e. diameter ?4) is asymptotically for constants A,B as n→∞. This is proved by using a natural correspondence between partitions of integers and star-like trees.     

Permutations selon leurs pics,creux, doubles montées et double descentes,nombres d'euler et nombres de Genocchi

We study permutations whose type is given, the type being the sets of the values of the peaks, throughs, doubles rises and double falls. We show that the type of a permutation on n letters is caracterized by a map γ[n]→[n]; the number of possible types is the Catalan number; the number of permutations whose type is associated with γ is the product γ(1)γ(2)·γ(n). This result is a corollary of an explicit bijection between permutations and pairs (γ, ?) where ? is a map dominated by γ. Specifying this bijection tG various classes of permutations provides enumerative formulas for classical numbers, e.g. Euler and Genocchi numbers. It has been proved recently that each enumerative formula of this work is equivalent to a continued fraction expansion of a generating serie.     

Graphs which,with their complements,have certain clique covering numbers

Two common invariants of a graph G are its node clique cover number, θ₀(G), and its edge clique cover number, θ₁(G). We present in this work a characterization of those graphs for which they and their complements, $\text{G}\text{?}$, have θ₀(G)=θ₁(G) and θ₀($\text{G}\text{?}$)=θ₁($\text{G}\text{?}$). Graphs satis ying these conditions are shown to constitute a subset of those graphs which we term C-graphs.     

Sato-Tate, cyclicity, and divisibility statistics on average for elliptic curves of small height

We obtain asymptotic formulae for the number of primes p ≤ x for which the reduction modulo p of the elliptic curve $$ E_{a,b} :Y^2 = X^3 + aX + b $$ satisfies certain “natural” properties, on average over integers a and b such that |a| ? A and |b| ? B, where A and B are small relative to x. More precisely, we investigate behavior with respect to the Sato-Tate conjecture, cyclicity, and divisibility of the number of points by a fixed integer m.     

Counting involutory, unimodal, and alternating signed permutations

In this work we count the number of involutory, unimodal, and alternating elements of the group of signed permutations B_n, and the group of even-signed permutations D_n. Recurrence relations, generating functions, and explicit formulas of the enumerating sequences are given.     

Knights, spies, games and ballot sequences

This paper solves the Knights and Spies Problem: In a room there are n people, each labelled with a unique number between 1 and n. A person may either be a knight or a spy. Knights always tell the truth, while spies may lie or tell the truth as they see fit. Each person in the room knows the identity of everyone else. Apart from this, all that is known is that strictly more knights than spies are present. Asking only questions of the form: ‘Person i, what is the identity of person j?’, what is the least number of questions that will guarantee to find the true identities of all n people? We present a questioning strategy that uses slightly less than 3n/2 questions, and prove that it is optimal by solving a related two-player game. The performance of this strategy is analysed using methods from the famous ballot-counting problem. We end by discussing two questions suggested by generalisations of the original problem.     

Irredundance, secure domination and maximum degree in trees

It is shown that the lower irredundance number and secure domination number of an n vertex tree T with maximum degree Δ?3, are bounded below by 2(n+1)/(2Δ+3)(T≠K_1,Δ) and (Δn+Δ-1)/(3Δ-1), respectively. The bounds are sharp and extremal trees are exhibited.