Search

For an arbitrary invariant ρ(G) of a graph Gthe ρ-edge stability number esρ(G) is the minimum number of edges of Gwhose removal results in a graph H⊆ Gwith ρ(H) ≠ ρ(G) or with E(H) = ∅.

A (graph) property 𝒫 is a class of simple finite graphs closed under isomorphisms. In this paper we consider generalizations of sum list colorings of graphs with respect to properties 𝒫.

Let G = (V,E) be a simple graph and for every edge e ∈ E let L(e) be a set (list) of available colors. The graph G is called L-edge colorable if there is a proper edge coloring c of G with c(e) ∈ L(e) for all e ∈ E. A function f : E → ℕ is called an edge choice function of G and G is said to be f-edge choosable if G is L-edge colorable for every list assignment L with |L(e)| = f(e) for all e ∈ E. Set size(f) = ∑e∈Ef(e) and define the sum choice index χ′sc(G) as the minimum of size(f) over all edge choice functions f of G.

Let P and Q be additive and hereditary graph properties, r, s ∈ N, r ≥ s, and [ℤr]sbe the set of all s-element subsets of ℤr. An (r, s)-fractional (P,Q)-total coloring of G is an assignment h : V (G) ∪ E(G) → [ℤr]ssuch that for each i ∈ ℤrthe following holds: the vertices of G whose color sets contain color i induce a subgraph of G with property P, edges with color sets containing color i induce a subgraph of G with property Q, and the color sets of incident vertices and edges are disjoint. If each vertex and edge of G is colored with a set of s consecutive elements of ℤrwe obtain an (r, s)-circular (P,Q)-total coloring of G. In this paper we present basic results on (r, s)-fractional/circular (P,Q)-total colorings. We introduce the fractional and circular (P,Q)-total chromatic number of a graph and we determine this number for complete graphs and some classes of additive and hereditary properties.

In 1960 Ore proved the following theorem: Let Gbe a graph of order n. If d(u) + d(v)≥nfor every pair of nonadjacent vertices uand v, then Gis hamiltonian. Since then for several other graph properties similar sufficient degree conditions have been obtained, so‐called “Ore‐type degree conditions”. In [R. J. Faudree, R. H. Schelp, A. Saito, and I. Schiermeyer, Discrete Math 307 (2007), 873–877], Faudree et al. strengthened Ore's theorem as follows: They determined the maximum number of pairs of nonadjacent vertices that can have degree sum less than n(i.e. violate Ore's condition) but still imply that the graph is hamiltonian. In this article we prove that for some other graph properties the corresponding Ore‐type degree conditions can be strengthened as well. These graph properties include traceable graphs, hamiltonian‐connected graphs, k‐leaf‐connected graphs, pancyclic graphs, and graphs having a 2‐factor with two components. Graph closures are computed to show these results. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 314–323, 2012

The Newton number or kissing number N(D) of a compact disc or a compact body D is the maximum number of non-overlapping congruent copies (neighbors) of D that can touch D without having interior points in common. We give a short and constructive proof of N(D) = 6 for arbitrary convex or non-convex discs D and we determine lower and upper bounds for the Newton number of isosceles triangles.

For alln> dthere existnpoints in the Euclidean spaceEdsuch that not all points are in a hyperplane and all mutual distances are integral. It is proved that the minimum diameter of such integral point sets has an upper bound of 2clognlog logn.