On semi‐classical d‐orthogonal polynomials

In this paper a general theory of semi‐classical d‐orthogonal polynomials is developed. We define the semi‐classical linear functionals by means of a distributional equation , where Φ and Ψ are matrix polynomials. Several characterizations for these semi‐classical functionals are given in terms of the corresponding d‐orthogonal polynomials sequence. They involve a quasi‐orthogonality property for their derivatives and some finite‐type relations.     

Sparse ramsey graphs

IfH is a Ramsey graph for a graphG thenH is rich in copies of the graphG. Here we prove theorems in the opposite direction. We find examples ofH such that copies ofG do not form short cycles inH. This provides a strenghtening also, of the following well-known result of Erdős: there exist graphs with high chromatic number and no short cycles. In particular, we solve a problem of J. Spencer. Dedicated to Paul Erdős on his seventieth birthday     

An introduction to the k-defect polynomials

The 0-defect polynomial of a graph is just the chromatic polynomial. This polynomial has been widely studied in the literature. Yet little is known about the properties of k-defect polynomials of graphs in general, when 0 < k ≤ |E(G)|. In this survey we give some properties of k-defect polynomials, in particular we highlight the properties of chromatic polynomials which also apply to k-defect polynomials. We discuss further research which can be done on the k-defect polynomials.     

H-extension of graphs

We consider the problem of constructing a graphG* from a collection of isomorphic copies of a graphG in such a way that for every two copies ofG, either no vertices or a section graph isomorphic to a graphH is identified. It is shown that ifG can be partitioned into vertex-disjoint copies ofH, thenG* can be made to have at most |H| orbits. A condition onG so thatG* can be vertextransitive is also included.     

Simple proof of the existence of restricted ramsey graphs by means of a partite construction

By means of a partite construction we present a short proof of the Galvin Ramsey property of the class of all finite graphs and of its strengthening proved in [5]. We also establish a generalization of those results. Further we show that for every positive integerm there exists a graphH which is Ramsey forK _m and does not contain two copies ofK _m with more than two vertices in common.     

RandomlyH-coverable graphs

A graph israndomly matchable if every matching of the graph is contained in a perfect matching. We generalize this notion and say that a graphG israndomly H-coverable if every set of independent subgraphs, each isomorphic toH, that does not cover the vertices ofG can be extended to a larger set of independent copies ofH. Various problems are considered for the situation whereH is a path. In particular, we characterize the graphs that are randomlyP ₃ -coverable.     

q‐Bernstein polynomials related to q‐Frobenius–Euler polynomials,l‐functions,and q‐Stirling numbers

The aim of this paper was to derive new identities and relations associated with the q‐Bernstein polynomials, q‐Frobenius–Euler polynomials, l‐functions, and q‐Stirling numbers of the second kind. We also give some applications related to theses polynomials and numbers. Copyright © 2012 John Wiley & Sons, Ltd.     

Homogeneous polynomials and extensions of Hardy‐Hilbert's inequality

If L is a continuous symmetric n‐linear form on a real or complex Hilbert space and $\widehat{L}$ is the associated continuous n‐homogeneous polynomial, then $\Vert L\Vert =\big \Vert \widehat{L}\big \Vert$. We give a simple proof of this well‐known result, which works for both real and complex Hilbert spaces, by using a classical inequality due to S. Bernstein for trigonometric polynomials. As an application, an open problem for the optimal lower bound of the norm of a homogeneous polynomial, which is a product of linear forms, is related to the so‐called permanent function of an n × n positive definite Hermitian matrix. We have also derived generalizations of Hardy‐Hilbert's inequality.     

New Ore‐Type Conditions for H‐Linked Graphs

For a fixed (multi)graph H, a graph G is H‐linked if any injection f: V(H)→V(G) can be extended to an H‐subdivision in G. The notion of an H ‐linked graph encompasses several familiar graph classes, including k‐linked, k‐ordered and k‐connected graphs. In this article, we give two sharp Ore‐type degree sum conditions that assure a graph G is H ‐linked for arbitrary H. These results extend and refine several previous results on H ‐linked, k‐linked, and k‐ordered graphs. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:69–77, 2012     

The asymptotic number of graphs not containing a fixed color-critical subgraph

For a finite graphG letForb(H) denote the class of all finite graphs which do not containH as a (weak) subgraph. In this paper we characterize the class of those graphsH which have the property that almost all graphs inForb(H) are -colorable. We show that this class corresponds exactly to the class of graphs whose extremal graph is the Turán-graphT _n ().An earlier result of Simonovits (Extremal graph problems with symmetrical extremal graphs. Additional chromatic conditions,Discrete Math. 7 (1974), 349–376) shows that these are exactly the (+1)-chromatic graphs which contain a color-critical edge.     

On zero-divisors of near-rings of polynomials

In this paper, we are interested to study zero-divisor properties of a 0-symmetric nearring of polynomials R₀[x], when R is a commutative ring. We show that for a reduced ring R, the set of all zero-divisors of R₀[x], namely Z(R₀[x]), is an ideal of R₀[x] if and only if Z(R) is an ideal of R and R has Property (A). For a non-reduced ring R, it is shown that Z(R₀[x]) is an ideal of Z(R₀[x]) if and only if ann_R({a, b}) ∩ N i?(R) ≠ 0, for each a, b ∈ Z(R). We also investigate the interplay between the algebraic properties of a 0-symmetric nearring of polynomials R₀[x] and the graph-theoretic properties of its zero-divisor graph. The undirected zero-divisor graph of R₀[x] is the graph Γ(R₀[x]) such that the vertices of Γ(R₀[x]) are all the non-zero zero-divisors of R₀[x] and two distinct vertices f and g are connected by an edge if and only if f ? g = 0 or g ? f = 0. Among other results, we give a complete characterization of the possible diameters of Γ(R₀[x]) in terms of the ideals of R. These results are somewhat surprising since, in contrast to the polynomial ring case, the near-ring of polynomials has substitution for its “multiplication” operation.     

Maximal σ‐polynomials of connected 3‐chromatic graphs

In the set of graphs of order n and chromatic number k the following partial order relation is defined. One says that a graph G is less than a graph H if c_i(G) ≤ c_i(H) holds for every i, k ≤ i ≤ n and at least one inequality is strict, where c_i(G) denotes the number of i‐color partitions of G. In this paper the first ? n/2 ? levels of the diagram of the partially ordered set of connected 3‐chromatic graphs of order n are described. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 210–222, 2003     

Greatest common divisors and least common multiples of graphs

A graphH divides a graphG, writtenH|G, ifG isH-decomposable. A graphG without isolated vertices is a greatest common divisor of two graphsG ₁ andG ₂ ifG is a graph of maximum size for whichG|G ₁ andG|G ₂, while a graphH without isolated vertices is a least common multiple ofG ₁ andG ₂ ifH is a graph of minimum size for whichG ₁|H andG ₂|H. It is shown that every two nonempty graphs have a greatest common divisor and least common multiple. It is also shown that the ratio of the product of the sizes of a greatest common divisor and least common multiple ofG ₁ andG ₂ to the product of their sizes can be arbitrarily large or arbitrarily small. Sizes of least common multiples of various pairsG ₁,G ₂ of graphs are determined, including when one ofG ₁ andG ₂ is a cycle of even length and the other is a star.G. C's research was supported in part by the Office of Naval Research, under Grant N00014-91-I-1060     

Vertex‐Transitive Graphs of Prime‐Squared Order Are Hamilton‐Decomposable

We prove that all connected vertex‐transitive graphs of order p², p a prime, can be decomposed into Hamilton cycles.     

3‐Factor‐Criticality of Vertex‐Transitive Graphs

A graph of order n is p ‐factor‐critical, where p is an integer of the same parity as n, if the removal of any set of p vertices results in a graph with a perfect matching. 1‐factor‐critical graphs and 2‐factor‐critical graphs are factor‐critical graphs and bicritical graphs, respectively. It is well known that every connected vertex‐transitive graph of odd order is factor‐critical and every connected nonbipartite vertex‐transitive graph of even order is bicritical. In this article, we show that a simple connected vertex‐transitive graph of odd order at least five is 3‐factor‐critical if and only if it is not a cycle.     

Perfect Graphs with No Balanced Skew‐Partition are 2‐Clique‐Colorable

A graph G is perfect if for all induced subgraphs H of G, . A graph G is Berge if neither G nor its complement contains an induced odd cycle of length at least five. The Strong Perfect Graph Theorem [9] states that a graph is perfect if and only if it is Berge. The Strong Perfect Graph Theorem was obtained as a consequence of a decomposition theorem for Berge graphs [M. Chudnovsky, Berge trigraphs and their applications, PhD thesis, Princeton University, 2003; M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas, The strong perfect graph theorem, Ann Math 164 (2006), 51–229.], and one of the decompositions in this decomposition theorem was the “balanced skew‐partition.” A clique‐coloring of a graph G is an assignment of colors to the vertices of G in such a way that no inclusion‐wise maximal clique of G of size at least two is monochromatic, and the clique‐chromatic number of G, denoted by , is the smallest number of colors needed to clique‐color G. There exist graphs of arbitrarily large clique‐chromatic number, but it is not known whether the clique‐chromatic number of perfect graphs is bounded. In this article, we prove that every perfect graph that does not admit a balanced skew‐partition is 2‐clique colorable. The main tool used in the proof is a decomposition theorem for “tame Berge trigraphs” due to Chudnovsky et al. ( http://arxiv.org/abs/1308.6444 ).     

Adjoint polynomials of bridge–path and bridge–cycle graphs and Chebyshev polynomials

The chromatic polynomial of a simple graph G with n>0 vertices is a polynomial of degree n, where α_k(G) is the number of k-independent partitions of G for all k. The adjoint polynomial of G is defined to be , where is the complement of G. We find explicit formulas for the adjoint polynomials of the bridge–path and bridge–cycle graphs. Consequence, we find the zeros of the adjoint polynomials of several families of graphs.     

On the Key Equation Over a Commutative Ring

We define alternant codes over a commutative ring R and a corresponding key equation. We show that when the ring is a domain, e.g. the p-adic integers, the error-locator polynomial is the unique monic minimal polynomial (equivalently, the unique shortest linear recurrence) of the finite sequence of syndromes and that it can be obtained by Algorithm MR of Norton.WhenR is a local ring, we show that the syndrome sequence may have more than one (monic) minimal polynomial, but that all the minimal polynomials coincide modulo the maximal ideal ofR . We characterise the set of minimal polynomials when R is a Hensel ring. We also apply these results to decoding alternant codes over a local ring R: it is enough to find any monic minimal polynomial over R and to find its roots in the residue field. This gives a decoding algorithm for alternant codes over a finite chain ring, which generalizes and improves a method of Interlando et. al. for BCH and Reed-Solomon codes over a Galois ring.     

‐differential equations for ‐classical polynomials and ‐Jacobi–Stirling numbers

We introduce, characterise and provide a combinatorial interpretation for the so‐called q‐Jacobi–Stirling numbers. This study is motivated by their key role in the (reciprocal) expansion of any power of a second order q‐differential operator having the q‐classical polynomials as eigenfunctions in terms of other even order operators, which we explicitly construct in this work. The results here obtained can be viewed as the q‐version of those given by Everitt et al. and by the first author, whilst the combinatorics of this new set of numbers is a q‐version of the Jacobi–Stirling numbers given by Gelineau and the second author.     

On permutation polynomials in two variables over ℤ/<Emphasis Type="Italic">p</Emphasis><Superscript>2</Superscript>ℤ

We give a good characterization of the permutation polynomials in two variables over Z/p2Z.