Search

The discrete boundary value problem for a fourth-order difference equation is discussed in this paper. The existence result of multiple solutions is established by restricting the algebraic assumptions on the nonlinear term and confirming the parameter μ in an interval related to eigenvalues. The main methods adopted are the critical point theorems applicable for the finite dimensional Banach space recently proposed by Bonanno et al. (2014).

For an integer s ≥ 0 , a graph G is s -hamiltonian if for any vertex subset S ⊆ V ( G ) with | S | ≤ s , G − S is hamiltonian, and G is s -hamiltonian connected if for any vertex subset S ⊆ V ( G ) with | S | ≤ s , G − S is hamiltonian connected. Thomassen in 1984 conjectured that every 4-connected line graph is hamiltonian (see Thomassen, 1986), and Kuczel and Xiong in 2004 conjectured that every 4-connected line graph is hamiltonian connected (see Ryjacek and Vrana, 2011). In Broersma and Veldman (1987), Broersma and Veldman raised the characterization problem of s -hamiltonian line graphs. In Lai and Shao (2013), it is conjectured that for s ≥ 2 , a line graph L ( G ) is s -hamiltonian if and only if L ( G ) is ( s + 2 ) -connected. In this paper we prove the following. (i) For an integer s ≥ 2 , the line graph L ( G ) of a claw-free graph G is s -hamiltonian if and only if L ( G ) is ( s + 2 ) -connected. (ii) The line graph L ( G ) of a claw-free graph G is 1-hamiltonian connected if and only if L ( G ) is 4-connected.

An antimagic labeling of a digraph D with n vertices and m arcs is a bijection from the set of arcs of D to { 1 , 2 , … , m } such that all n oriented vertex sums are pairwise distinct, where an oriented vertex sum of a vertex is the sum of labels of all arcs entering that vertex minus the sum of labels of all arcs leaving it. Hefetz, Mutze and Schwartz conjectured every connected undirected graph admits an antimagic orientation. In this paper, we support this conjecture by proving that every Halin graph admits an antimagic orientation.

Two errors in the original article are corrected so as to validate the major results. Thus, the digraphs that have the minimum and second minimum spectral radius among all strongly connected digraphs with given order and dichromatic number are determined.

For a positive integer k , a graph is k -knitted if for each subset S of k vertices, and every partition of S into (disjoint) parts S 1 , … , S t for some t ≥ 1 , one can find disjoint connected subgraphs C 1 , … , C t such that C i contains S i for each i ∈ [ t ] ≔ { 1 , 2 , … , t } . In this article, we show that if the minimum degree of an n -vertex graph G is at least n ∕ 2 + k ∕ 2 − 1 when n ≥ 2 k + 3 , then G is k -knitted. The minimum degree is sharp. As a corollary, we obtain that k -contraction-critical graphs are k 8 -connected.

It is trivial that every 3-polytope has a face of degree at most 5, called minor. Back in 1940, Lebesgue gave an approximate description of minor faces in 3-polytopes, depending on 17 main parameters. In 2002, Borodin improved Lebesgue’s description on six parameters without worsening the others and suggested to find a tight description of minor faces. So far, such a tight description has been obtained only for several restricted classes of 3-polytopes: those with minimum degree 5 (Borodin, 1989), without vertices of degree 3 (Borodin and Ivanova, 2013), for plane triangulations (Borodin et al. 2014), and without vertices of degree from 4 to 7 (Borodin et al. 2017). In this paper, we consider 3-polytopes without vertices of degree from 5 to 7. A face is of type ( k 1 , k 2 , … ) if the set of degrees of its incident vertices is majorized by the vector ( k 1 , k 2 , … ) . It follows from results by Horňak and Jendrol’ (1996) that every such polytope has a face of one of the types ( 4 , 4 , ∞ ) , ( 3 , 8 , 15 ) , ( 3 , 9 , 14 ) , ( 3 , 10 , 13 ) , ( 3 , 3 , 3 , ∞ ) , ( 3 , 3 , 4 , 11 ) , ( 3 , 4 , 4 , 4 ) , and ( 3 , 3 , 3 , 3 , 4 ) , which improves four parameters in what can be obtained from Lebesgue’s description. We prove a tight description “ ( 4 , 4 , ∞ ) , ( 3 , 8 , 14 ) , ( 3 , 9 , 13 ) , ( 3 , 10 , 12 ) , ( 3 , 3 , 3 , ∞ ) , ( 3 , 3 , 4 , 11 ) , ( 3 , 4 , 4 , 4 ) , ( 3 , 3 , 3 , 3 , 4 ) ” and, in particular, give constructions (unexpected for us) showing that 13 and 11 here are best possible (constructions confirming the sharpness of the other parameters were known before).

Let p be an odd prime, and λ be a nonzero element of the finite field F p m . The λ -constacyclic codes of length 2 p s over F p m are classified as the ideals of quotient ring F p m [ x ] 〈 x 2 p s − λ 〉 in terms of their generator polynomials. Based on these generator polynomials, the symbol-pair distances of all such λ -constacyclic codes of length 2 p s are obtained in this paper. As an application, all MDS symbol-pair constacyclic codes of length 2 p s over F p m are established, which produce many new MDS symbol-pair codes with good parameters.

An edge of a k -connected graph is said to be k -contractible if its contraction results in a k -connected graph. A k -connected graph without k -contractible edge is said to be contraction critically k -connected. Y. Egawa and W. Mader, independently, showed that the minimum degree of a contraction critical k -connected graph is at most 5 k 4 − 1 . Hence, the minimum degree of a contraction critical 8-connected graph is either 8 or 9. This paper shows that a graph G is a contraction critical 8-connected graph with minimum degree 9 if and only if G is the strong product of a contraction critical 4-connected graph H and K 2 .

An acyclic k -coloring of a graph G is a proper vertex coloring using k colors such that any cycle of G is colored with at least three colors, and the minimum integer k is called the acyclic chromatic number of G , denoted by χ a ( G ) . Grunbaum conjectured that the acyclic chromatic number of graphs with maximum degree at most Δ is no more than Δ + 1 in 1973. By now, the conjecture has been proved only for Δ ≤ 4 . We show that χ a ( G ) ≤ 9 for Δ ≤ 6 , which improves the result χ a ( G ) ≤ 10 of Zhao et al. (2014).

For a hypergraph H = ( V , E ) , a subfamily C ⊆ E is called a cover of the hypergraph if ⋃ C = ⋃ E . A cover C is called minimal if each cover D ⊆ C of the hypergraph H coincides with C . We prove that for a hypergraph H the following conditions are equivalent: (i) each countable subhypergraph of H has a minimal cover; (ii) each non-empty subhypergraph of H has a maximal edge; (iii) H contains no isomorphic copy of the hypergraph ( ω , ω ) . This characterization implies that a countable hypergraph ( V , E ) has a minimal cover if every infinite set I ⊆ V contains a finite subset F ⊆ I such that the family of edges E F ≔ { E ∈ E : F ⊆ E } is finite. Also we prove that a hypergraph ( V , E ) has a minimal cover if sup { | E | : E ∈ E } ω or for every v ∈ V the family E v ≔ { E ∈ E : v ∈ E } is finite.

A Dyck path is non-decreasing if the y -coordinates of its valleys form a non-decreasing sequence. In this paper we give enumerative results and some statistics of several aspects of non-decreasing Dyck paths. We give the number of pyramids at a fixed level that the paths of a given length have, count the number of primitive paths, count how many of the non-primitive paths can be expressed as a product of primitive paths, and count the number of paths of a given height and a given length. We present and prove our results using combinatorial arguments, generating functions (using the symbolic method) and parameterize the results studied here using the Riordan arrays. We use known bijections to connect direct column-convex polyominoes, Elena trees, and non-decreasing Dyck paths.

A graph is ( k 1 , k 2 ) -colorable if it admits a vertex partition into a graph with maximum degree at most k 1 and a graph with maximum degree at most k 2 . We show that every ( C 3 , C 4 , C 6 ) -free planar graph is ( 0 , 6 ) -colorable. We also show that deciding whether a ( C 3 , C 4 , C 6 ) -free planar graph is ( 0 , 3 ) -colorable is NP-complete.

Let f r ( n ) represent the minimum number of complete r -partite r -graphs required to partition the edge set of the complete r -uniform hypergraph on n vertices. The Graham–Pollak theorem states that f 2 ( n ) = n − 1 . An upper bound of ( 1 + o ( 1 ) ) n ⌊ r 2 ⌋ was known. Recently this was improved to 14 15 ( 1 + o ( 1 ) ) n ⌊ r 2 ⌋ for even r ≥ 4 . A bound of [ r 2 ( 14 15 ) r 4 + o ( 1 ) ] ( 1 + o ( 1 ) ) n ⌊ r 2 ⌋ was also proved recently. Let c r be the limit of f r ( n ) n ⌊ r 2 ⌋ as n → ∞ . The smallest odd r for which c r 1 that was known was for r = 295 . In this note we improve this to c 113 1 and also give better upper bounds for f r ( n ) , for small values of even r .

In 1984, Wilson proved the Erdős–Ko–Rado theorem for t -intersecting families of k -subsets of an n -set: he showed that if n ≥ ( t + 1 ) ( k − t + 1 ) and F is a family of k -subsets of an n -set such that any two members of F have at least t elements in common, then | F | ≤ n − t k − t . His proof made essential use of a matrix whose origin is not obvious. In this paper we show that this matrix can be derived, in a sense, as a projection of t - ( n , k , 1 ) design.

For a given graph G = (V, E), the degree mean rate of an edge uv ∈ E is a half of the quotient between the geometric and arithmetic means of its end-vertex degrees d(u) and d(v). In this note, we derive tight bounds for the Randić index of G in terms of its maximum and minimum degree mean rates over its edges. As a consequence, we prove the known conjecture that the average distance is bounded above by the Randić index for graphs with order n large enough, when the minimum degree δ is greater than (approximately) ∆1/3 , where ∆ is the maximum degree. As a by-product, this proves that almost all random (Erdös-Rényi) graphs satisfy the conjecture. This research is partially supported by the project 017SGR1087 of the Agency for the Management of University and Research Grants (AGAUR) of the Government of Catalonia. This research has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922.

If G is a finite group and k = q > 2 or k = q + 1 for a prime power q then, for infinitely many integers v , there is a 2- ( v , k , 1 ) -design D for which Aut D ≅ G .

Given a graph G we are interested in studying the symmetric matrices associated to G with a fixed number of negative eigenvalues. For this class of matrices we focus on the maximum possible nullity. For trees this parameter has already been studied and plenty of applications are known. In this work we derive a formula for the maximum nullity and completely describe its behavior as a function of the number of negative eigenvalues. In addition, we also carefully describe the matrices associated with trees that attain this maximum nullity. The analysis is then extended to the more general class of unicyclic graphs. Further our work is applied to re-describing all possible partial inertias associated with trees, and is employed to study an instance of the inverse eigenvalue problem for certain trees.

A homeomorphically irreducible spanning tree (HIST) of a connected graph is a spanning tree without vertices of degree two. The determination of the existence problem of a homeomorphically irreducible spanning tree in a plane cubic graph is NP-complete. A hexangulation of a surface is a cubic graph embedded on a surface such that every face is bounded by a hexagon. It is a problem asked by Hoffmann-Ostenhof and Ozeki that whether there are finitely or infinitely many hexangulations of torus with homeomorphically irreducible spanning trees. In this paper, we show that a family of hexangulations of surfaces, denoted by H ( m , n ) , have a homeomorphically irreducible spanning tree if and only if it has an odd number of faces, which answers the problem of Hoffmann-Ostenhof and Ozeki for hexangulations of surfaces.

A ( k , g ) -graph is a k -regular graph with girth g and a ( k , g ) -cage is a ( k , g ) -graph with the fewest possible number of vertices n ( k , g ) . Constructing ( k , g ) -cages and determining the order are both very hard problems. For this reason, an intensive line of research is devoted to constructing smaller ( k , g ) -graphs than previously known ones, providing in this way new upper bounds to n ( k , g ) each time such a graph is constructed. The paper focuses on girth g = 5 , where cages are known only for degrees k ≤ 7 . We construct ( k , 5 ) -graphs using and extending techniques of amalgamation into the incidence graphs of elliptic semiplanes of type L introduced and exposed by Funk (2009). The order of these graphs provides better upper bounds on n ( k , 5 ) than those known so far, for values of k such that either 13 ≤ k ≤ 33 or k ≥ 66 .

“Which graphs are determined by their spectrum (DS for short)?” is a fundamental question in spectral graph theory. It is generally very hard to show a given graph to be DS and few results about DS graphs are known in literature. In this paper, we consider the above problem in the context of the generalized Q -spectrum. A graph G is said to be determined by the generalized Q -spectrum (DGQS for short) if, for any graph H , H and G have the same Q -spectrum and so do their complements imply that H is isomorphic to G . We give a simple arithmetic condition for a graph being DGQS. More precisely, let G be a graph with adjacency matrix A and degree diagonal matrix D . Let Q = A + D be the signless Laplacian matrix of G , and W Q ( G ) = [ e , Q e , … , Q n − 1 e ] ( e is the all-ones vector) be the Q -walk matrix. We show that if det W Q ( G ) 2 ⌊ 3 n − 2 2 ⌋ (which is always an integer) is odd and square-free, then G is DGQS.

For n ≥ k ≥ 4 , let A R X + Y = Z + T k ( n ) be the maximum number of rainbow solutions to the Sidon equation X + Y = Z + T over all k -colorings c : [ n ] → [ k ] . It can be shown that the total number of solutions in [ n ] to the Sidon equation is n 3 ∕ 12 + O ( n 2 ) and so, trivially, A R X + Y = Z + T k ( n ) ≤ n 3 ∕ 12 + O ( n 2 ) . We improve this upper bound to A R X + Y = Z + T k ( n ) ≤ 1 12 − 1 24 k n 3 + O k ( n 2 ) for all n ≥ k ≥ 4 . Furthermore, we give an explicit k -coloring of [ n ] with more rainbow solutions to the Sidon equation than a random k -coloring, and gives a lower bound of 1 12 − 1 3 k n 3 − O k ( n 2 ) ≤ A R X + Y = Z + T k ( n ) . When k = 4 , we use a different approach based on additive energy to obtain an upper bound of 3 n 3 ∕ 96 + O ( n 2 ) , whereas our lower bound is 2 n 3 ∕ 96 − O ( n 2 ) in this case.

We consider the problem of sending a message from a sender s to a receiver r through an unreliable network by specifying in a protocol what each vertex is supposed to do if it receives the message from one of its neighbors. A protocol for routing a message in such a graph is finite if it never floods r with an infinite number of copies of the message. The expected reliability of a given protocol is the probability that a message sent from s reaches r when the edges of the network fail independently with probability 1 − p . We discuss, for given networks, the properties of finite protocols with maximum expected reliability in the case when p is close to 0 or 1, and we describe networks for which no one protocol is optimal for all values of p . In general, finding an optimal protocol for a given network and fixed probability is challenging and many open problems remain.

A natural link between the notions of majorization and strongly Sperner posets is elucidated. It is then used to obtain a variety of consequences, including new R\'enyi entropy inequalities for sums of independent, integer-valued random variables., Comment: Introduction was completely rewritten and there are numerous corrections. Expansion of background on Sperner theory, and several references are added

A conjecture widely attributed to Neumann is that all finite non-desarguesian projective planes contain a Fano subplane. In this note, we show that any finite projective plane of even order which admits an orthogonal polarity contains many Fano subplanes. The number of planes of order less than n previously known to contain a Fano subplane was O ( log n ) , whereas the number of planes of order less than n that our theorem applies to is not bounded above by any polynomial in n .

Let G = ( V 1 , V 2 ; E ) be a bipartite graph with | V 1 | = | V 2 | ≥ 3 k , where k is a positive integer. We prove that if the minimum degree of G is at least 2 k + 1 , then G admits k vertex-disjoint cycles such that each of them has at least two chords. This is a bipartite counterpart of the result due to P. Balister, H. Li and R. Schelp.

We consider the second weighted Bartholdi zeta function of a graph G , and present weighted versions for the results of Li and Hou’s on the partial derivatives of the determinant part in the determinant expression of the Bartholdi zeta function of G . Furthermore, we give a formula for the weighted Kirchhoff index of a regular covering of G in terms of that of G .

Let G be a simple connected graph with n vertices and m edges. The spectral radius ρ ( G ) of G is the largest eigenvalue of its adjacency matrix. In this paper, we firstly consider the effect on the spectral radius of a graph by removing a vertex, and then as an application of the result, we obtain a new sharp upper bound of ρ ( G ) which improves some known bounds: If ( k − 2 ) ( k − 3 ) 2 ≤ m − n ≤ k ( k − 3 ) 2 , where k ( 3 ≤ k ≤ n ) is an integer, then ρ ( G ) ≤ 2 m − n − k + 5 2 + 2 m − 2 n + 9 4 . The equality holds if and only if G is a complete graph K n or K 4 − e , where K 4 − e is the graph obtained from K 4 by deleting some edge e .

In this article we introduce a new matroid invariant, a combinatorial analog of the topological zeta function of a polynomial. More specifically we associate to any ranked, atomic meet-semilattice L a rational function Z L ( s ) , in such a way that when L is the lattice of flats of a complex hyperplane arrangement we recover the usual topological zeta function. The definition is in terms of a choice of a combinatorial analog of resolutions of singularities, and the main result is that Z L ( s ) does not depend on this choice and depends only on L . Known properties of the topological zeta function provide a source of potential ℂ -realisability test for matroids.

A canonical double cover B ( X ) of a graph X is the direct product of X and the complete graph K 2 on two vertices. In order to answer the question when a canonical double cover of a given graph is a Cayley graph, in 1992 Marusic et al. introduced the concept of generalized Cayley graphs. In this paper this concept is generalized to a wider class of graphs, the so-called extended generalized Cayley graphs. It is proved that the canonical double cover of a connected non-bipartite graph X is a Cayley graph if and only if X is an extended generalized Cayley graph. This corrects an incorrectly stated claim in [Discrete Math. 102 (1992), 279–285].

Let n and k be positive integers with n > k . Given a permutation ( π 1 , … , π n ) of integers 1 , … , n , we consider k -consecutive sums of π , i.e., s i ≔ ∑ j = 0 k − 1 π i + j for i = 1 , … , n , where we let π n + j = π j . What we want to do in this paper is to know the exact value of msum ( n , k ) ≔ min max { s i : i = 1 , … , n } − k ( n + 1 ) 2 : π ∈ S n , where S n denotes the set of all permutations of 1 , … , n . In this paper, we determine the exact values of msum ( n , k ) for some particular cases of n and k . As a corollary of the results, we obtain msum ( n , 3 ) , msum ( n , 4 ) and msum ( n , 6 ) for any n .

We give a new Jacobi--Trudi-type formula for characters of finite-dimensional irreducible representations in type $C_n$ using characters of the fundamental representations and non-intersecting lattice paths. We give equivalent determinant formulas for the decomposition multiplicities for tensor powers of the spin representation in type $B_n$ and the exterior representation in type $C_n$. This gives a combinatorial proof of an identity of Katz and equates such a multiplicity with the dimension of an irreducible representation in type $C_n$. By taking certain specializations, we obtain identities for $q$-Catalan triangle numbers, the $q,t$-Catalan number of Stump, $q$-triangle versions of Motzkin and Riordan numbers, and generalizations of Touchard's identity. We use (spin) rigid tableaux and crystal base theory to show some formulas relating Catalan, Motzkin, and Riordan triangle numbers., Comment: 68 pages, 8 figures

A loop L is strongly admissible if there exists a bijection ϕ : L → L for which the mappings g ↦ g ϕ ( g ) and g ↦ g ( g ϕ ( g ) ) are both bijections. We derive some results on the strong admissibility of finite nonassociative Moufang loops, constructed from groups using the Chein constructions.

The eccentricity matrix E ( G ) of a graph G is derived from the distance matrix by keeping for each row and each column only the eccentricities. The E -eigenvalues of a graph G are those of its eccentricity matrix E ( G ) , and the eccentricity energy (or the E -energy) of G is the sum of the absolute values of E -eigenvalues. A graph is called self-centered graph if its diameter and radius are equal. In this paper, we investigate the relation between the E -energy and the ordinary energy, and we determine the exact values of E -energies of paths, cycles and double stars. Moreover, when G is an r -antipodal graph, we show that the E -energy of strong product of graphs G and H only depends on the structure of G . We finally provide upper and lower bounds for the E -energy whose extreme graphs are kinds of self-centered graphs, and we propose some potential topics for further study.

Suppose the edges of K n are assigned weights by a weight function w . We define the weighted extremal number ex ( n , w , F ) ≔ max { w ( G ) ∣ G ⊆ K n , and G is F -free } where w ( G ) ≔ ∑ e ∈ E ( G ) w ( e ) . In this paper we study this problem for two types of weights w , each of which has an application. The first application is to an extremal problem in a complete multipartite host graph. The second application is to the maximum rectilinear crossing number of trees of diameter 4.

We introduce the operators F i on permutation π = π 1 ⋯ π k − 1 1 π k + 1 ⋯ π n of { 1 , 2 , … , n } , where 1 ≤ i ≤ k − 1 , i.e., define F i ( π ) = π 1 ′ π 2 ′ ⋯ π n ′ as π j ′ = π j − 1 for 1 ≤ j ≤ i , and π i + 1 ′ π i + 2 ′ ⋯ π n ′ has the same relative order as π i + 1 π i + 2 ⋯ π n . The operators F i have many properties concerning the 132-pattern and inversions. Furthermore, we find that the operators F i can be characterized by a series of swaps of two entries. Two applications of the operators are given. As a first application, we obtain some new objects in 132-avoiding permutations and in Dyck paths that are enumerated by the entries in Catalan’s triangle. As another application, we give an algorithm to generate the set of permutations of length n + 1 with k inversions from the set of permutations of length n with k inversions when n ≥ k + 1 .

A graph is traceable if it contains a Hamiltonian path. We present a connected non-traceable cubic bipartite planar graph with 52 vertices and prove that there are no smaller such graphs.

Let F 2 m be a finite field of cardinality 2 m , R = F 2 m [ u ] ∕ 〈 u 4 〉 = F 2 m + u F 2 m + u 2 F 2 m + u 3 F 2 m ( u 4 = 0 ) which is a finite chain ring, and n is an odd positive integer. For any δ , α ∈ F 2 m × , an explicit representation for the dual code of any ( δ + α u 2 ) -constacyclic code over R of length 2 n is given. And some dual codes of ( 1 + u 2 ) -constacyclic codes over R of length 14 are constructed. For the case of δ = 1 , all distinct self-dual ( 1 + α u 2 ) -constacyclic codes over R of length 2 n are determined.

The Delannoy numbers d ( n , k ) count the number of lattice paths from ( 0 , 0 ) to ( n − k , k ) using steps ( 1 , 0 ) , ( 0 , 1 ) and ( 1 , 1 ) . We show that the zeros of all Delannoy polynomials d n ( x ) = ∑ k = 0 n d ( n , k ) x k are in the open interval ( − 3 − 2 2 , − 3 + 2 2 ) and are dense in the corresponding closed interval. We also show that the Delannoy numbers d ( n , k ) are asymptotically normal (by central and local limit theorems).

The Alon–Tarsi conjecture states that if n is even, then the sum of the signs of the Latin squares of order n is non-zero (Alon and Tarsi, 1992). The conjecture has been proven in the cases n = p + 1 (Drisko, 1997), and n = p − 1 (Glynn, 2010), where p is an odd prime. This paper is intended to be a concise and largely self-contained account of these results, along with streamlined, and in some cases, original proofs that should be readily accessible to a mathematician with a background in combinatorics. We also discuss the relation between the Alon–Tarsi conjecture and Rota’s basis conjecture (Huang and Rota, 1994), and present some related problems, such as Zappa’s extension of the Alon–Tarsi conjecture (Zappa, 1997), and Drisko’s proof of the extended conjecture for n = p (Drisko, 1998).

The Hamilton–Waterloo Problem HWP ( v ; m , n ; α , β ) asks for a 2-factorization of the complete graph K v or K v − I , the complete graph with the edges of a 1-factor removed, into α C m -factors and β C n -factors, where 3 ≤ m n . In the case that m and n are both even, the problem has been solved except possibly when 1 ∈ { α , β } or when α and β are both odd, in which case necessarily v ≡ 2 ( mod 4 ) . In this paper, we develop a new construction that creates factorizations with larger cycles from existing factorizations under certain conditions. This construction enables us to show that there is a solution to HWP ( v ; 2 m , 2 n ; α , β ) for odd α and β whenever the obvious necessary conditions hold, except possibly if β = 1 ; β = 3 and gcd ( m , n ) = 1 ; α = 1 ; or v = 2 m n ∕ gcd ( m , n ) . This result almost completely settles the existence problem for even cycles, other than the possible exceptions noted above.

In this paper, we establish the existence of O’Nan configurations in all nonclassical ovoidal Buekenhout–Metz unitals in PG ( 2 , q 2 ) .

In 2003, Kostochka, Pelsmajer, and West introduced a list analogue of equitable coloring called equitable choosability. In this paper, we motivate and define a new list analogue of equitable coloring called proportional choosability. A $k$-assignment $L$ for a graph $G$ specifies a list $L(v)$ of $k$ available colors for each vertex $v$ of $G$. An $L$-coloring assigns a color to each vertex $v$ from its list $L(v)$. For each color $c$, let $\eta(c)$ be the number of vertices $v$ whose list $L(v)$ contains $c$. A proportional $L$-coloring of $G$ is a proper $L$-coloring in which each color $c \in \bigcup_{v \in V(G)} L(v)$ is used $\lfloor \eta(c)/k \rfloor$ or $\lceil \eta(c)/k \rceil$ times. A graph $G$ is proportionally $k$-choosable if a proportional $L$-coloring of $G$ exists whenever $L$ is a $k$-assignment for $G$. We show that if a graph $G$ is proportionally $k$-choosable, then every subgraph of $G$ is also proportionally $k$-choosable and also $G$ is proportionally $(k+1)$-choosable, unlike equitable choosability for which analogous claims would be false. We also show that any graph $G$ is proportionally $k$-choosable whenever $k \geq \Delta(G) + \lceil |V(G)|/2 \rceil$, and we use matching theory to completely characterize the proportional choosability of stars and the disjoint union of cliques., Comment: 21 pages

9 pages, 1 figure; International audience; We prove Terao conjecture saying that the freeness is determined by the combinatorics for arrangements of 13 lines in the complex projective plane.

In this paper we investigate bounds on set multipartite Ramsey numbers for the bipartite graph K 2 , n , extending or improving well-known upper bounds by Chung and Graham, Irving, Lortz and Mengersen. Known constructions based on certain classes of combinatorial designs (projective plane, Hadamard matrix, strongly regular graph) yield near-optimal bounds. As the main goal, a new construction based on strongly regular graph and Hadamard matrix produces a sharp class, generalizing a classical bound by Exoo, Harborth, and Mengersen.

A signed graph is a pair Γ = ( G , σ ) , where x = ( V ( G ) , E ( G ) ) is a graph and σ : E ( G ) → { + 1 , − 1 } is the sign function on the edges of G . For any α ∈ [ 0 , 1 ] we consider the matrix A α ( Γ ) = α D ( G ) + ( 1 − α ) A ( Γ ) , where D ( G ) is the diagonal matrix of the vertex degrees of G , and A ( Γ ) is the adjacency matrix of Γ . Let m A α ( Γ ) ( α ) be the multiplicity of α as an A α ( Γ ) -eigenvalue, and let G have p ( G ) pendant vertices, q ( G ) quasi-pendant vertices, and no components isomorphic to K 2 . It is proved that m A α ( Γ ) ( α ) = p ( G ) − q ( G ) whenever all internal vertices are quasi-pendant. If this is not the case, it turns out that m A α ( Γ ) ( α ) = p ( G ) − q ( G ) + m N α ( Γ ) ( α ) , where m N ( Γ ) ( α ) denotes the multiplicity of α as an eigenvalue of the matrix N α ( Γ ) obtained from A α ( Γ ) taking the entries corresponding to the internal vertices which are not quasi-pendant. Such results allow to state a formula for the multiplicity of 1 as an eigenvalue of the Laplacian matrix L ( Γ ) = D ( G ) − A ( Γ ) . Furthermore, it is detected a class G of signed graphs whose nullity – i.e. the multiplicity of 0 as an A ( Γ ) -eigenvalue – does not depend on the chosen signature. The class G contains, among others, all signed trees and all signed lollipop graphs. It also turns out that for signed graphs belonging to a subclass G ′ ⊂ G the multiplicity of 1 as Laplacian eigenvalue does not depend on the chosen signatures. Such subclass contains trees and circular caterpillars.

Assume that the vertices of a graph G are always operational, but the edges of G fail independently with probability q ∈ [ 0 , 1 ] . The all-terminal reliability of G is the probability that the resulting subgraph is connected. The all-terminal reliability can be formulated into a polynomial in q , and it was conjectured that all the roots of (nonzero) reliability polynomials fall inside the closed unit disk. It has since been shown that there exist some connected graphs which have their reliability roots outside the closed unit disk, but these examples seem to be few and far between, and the roots are only barely outside the disk. In this paper we generalize the notion of reliability to simplicial complexes and matroids and investigate when the roots fall inside the closed unit disk. We show that such is the case for matroids of rank 3 and paving matroids of rank 4. We also prove that the reliability roots of shellable complexes are dense in the complex plane, and that the real reliability roots of any matroid lie in [ − 1 , 0 ) ∪ { 1 } . Finally, we also show that the reliability roots of thickenings of the Fano matroid can lie outside the unit disk.

Over finite local Frobenius non-chain rings with nilpotency index 3 and when the length of the codes is relatively prime to the characteristic of the residue field of the ring, the structure of the dual of γ -constacyclic codes is established and the algebraic characterization of self-dual γ -constacyclic codes, reversible γ -constacyclic codes and γ -constacyclic codes with complementary dual are given. Generators for the dual code are obtained from those of the original constacyclic code.

In 1940, Lebesgue proved that every 3-polytope with minimum degree 5 contains a 5-vertex for which the set of degrees of its neighbors is majorized by one of the following sequences: ( 6 , 6 , 7 , 7 , 7 ) , ( 6 , 6 , 6 , 7 , 9 ) , ( 6 , 6 , 6 , 6 , 11 ) , ( 5 , 6 , 7 , 7 , 8 ) , ( 5 , 6 , 6 , 7 , 12 ) , ( 5 , 6 , 6 , 8 , 10 ) , ( 5 , 6 , 6 , 6 , 17 ) , ( 5 , 5 , 7 , 7 , 13 ) , ( 5 , 5 , 7 , 8 , 10 ) , ( 5 , 5 , 6 , 7 , 27 ) , ( 5 , 5 , 6 , 6 , ∞ ) , ( 5 , 5 , 6 , 8 , 15 ) , ( 5 , 5 , 6 , 9 , 11 ) , ( 5 , 5 , 5 , 7 , 41 ) , ( 5 , 5 , 5 , 8 , 23 ) , ( 5 , 5 , 5 , 9 , 17 ) , ( 5 , 5 , 5 , 10 , 14 ) , ( 5 , 5 , 5 , 11 , 13 ) . Recently, we proved that forbidding vertices of degree from 7 to 11 results in a tight description ( 5 , 5 , 6 , 6 , ∞ ) , ( 5 , 6 , 6 , 6 , 15 ) , ( 6 , 6 , 6 , 6 , 6 ) . The purpose of this note is to prove that every 3-polytope with minimum degree 5 and no vertices of degrees 6, 7, and 8 has a 5-vertex whose neighborhood is majorized by one of the sequences ( 5 , 5 , 5 , 5 , ∞ ) and ( 5 , 5 , 5 , 10 , 12 ) , which is tight and improves a corresponding description ( 5 , 5 , 5 , 5 , ∞ ) , ( 5 , 5 , 9 , 5 , 17 ) , ( 5 , 5 , 10 , 5 , 14 ) , ( 5 , 5 , 11 , 5 , 13 ) that follows from the Lebesgue Theorem.

A bi-block graph is a connected graph all of whose blocks are complete bipartite graphs. We give a combinatorial interpretation of the Moore–Penrose inverse of the incidence matrix of a complete multipartite graph and a bi-block graph.

A graph G is l -hamiltonian if each linear forest F with l edges contained in G can be extended to a hamiltonian cycle of G . We give a sharp upper bound for the maximum number of cliques of a fixed size in a non- l -hamiltonian graph. Furthermore, we prove stability: if a non- l -hamiltonian graph contains almost the maximum number of cliques, then it is a subgraph of one of two extremal graphs.