An evolutionary formulation of the crossing number problem.
An exact performance bound for an time greedy matching procedure.
An exploration of the permanent-determinant method.
An Extension of Kotzig’s Theorem
In 1955, Kotzig proved that every 3-connected planar graph has an edge with the degree sum of its end vertices at most 13, which is tight. An edge uv is of type (i, j) if d(u) ≤ i and d(v) ≤ j. Borodin (1991) proved that every normal plane map contains an edge of one of the types (3, 10), (4, 7), or (5, 6), which is tight. Cole, Kowalik, and Škrekovski (2007) deduced from this result by Borodin that Kotzig’s bound of 13 is valid for all planar graphs with minimum degree δ at least 2 in which every...
An extension of Kotzig’s theorem on the minimum weight of edges in -polytopes
An extremal characterization of projective planes.
An extremal problem for some classes of oriented graphs
An extremal problem on potentially -graphic sequences.
An extremal property of Turán graphs.
An extremal result for graphs with an application to their colourings.
An extremal theorem in the hypercube.
An identity between the determinant and the permanent of Hessenberg-type matrices
In this short note we provide an extension of the notion of Hessenberg matrix and observe an identity between the determinant and the permanent of such matrices. The celebrated identity due to Gibson involving Hessenberg matrices is consequently generalized.
An identity for the independence polynomials of trees.
An Implicit Weighted Degree Condition For Heavy Cycles
For a vertex v in a weighted graph G, idw(v) denotes the implicit weighted degree of v. In this paper, we obtain the following result: Let G be a 2-connected weighted graph which satisfies the following conditions: (a) The implicit weighted degree sum of any three independent vertices is at least t; (b) w(xz) = w(yz) for every vertex z ∈ N(x) ∩ N(y) with xy /∈ E(G); (c) In every triangle T of G, either all edges of T have different weights or all edges of T have the same weight. Then G contains...
An improved bound on the minimal number of edges in color-critical graphs.
An improved inductive definition of two restricted classes of triangulations of the plane
An improvement to Mathon's cyclotomic Ramsey colorings.
An inductive proof of Whitney's Broken Circuit Theorem
We present a new proof of Whitney's broken circuit theorem based on induction on the number of edges and the deletion-contraction formula.
An inequality chain of domination parameters for trees
We prove that the smallest cardinality of a maximal packing in any tree is at most the cardinality of an R-annihilated set. As a corollary to this result we point out that a set of parameters of trees involving packing, perfect neighbourhood, R-annihilated, irredundant and dominating sets is totally ordered. The class of trees for which all these parameters are equal is described and we give an example of a tree in which most of them are distinct.
An inequality concerning edges of minor weight in convex 3-polytopes
Let be the number of edges in a convex 3-polytope joining the vertices of degree i with the vertices of degree j. We prove that for every convex 3-polytope there is ; moreover, each coefficient is the best possible. This result brings a final answer to the conjecture raised by B. Grünbaum in 1973.