All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 64 Next

Displaying 1261 – 1280 of 1336

Showing per page

Onq-Power Cycles in Cubic Graphs

Julien Bensmail (2017)

Discussiones Mathematicae Graph Theory

In the context of a conjecture of Erdős and Gyárfás, we consider, for any q ≥ 2, the existence of q-power cycles (i.e., with length a power of q) in cubic graphs. We exhibit constructions showing that, for every q ≥ 3, there exist arbitrarily large cubic graphs with no q-power cycles. Concerning the remaining case q = 2 (which corresponds to the conjecture of Erdős and Gyárfás), we show that there exist arbitrarily large cubic graphs whose all 2-power cycles have length 4 only, or 8 only.

Optimal Backbone Coloring of Split Graphs with Matching Backbones

Krzysztof Turowski (2015)

Discussiones Mathematicae Graph Theory

For a graph G with a given subgraph H, the backbone coloring is defined as the mapping c : V (G) → N+ such that |c(u) − c(v)| ≥ 2 for each edge {u, v} ∈ E(H) and |c(u) − c(v)| ≥ 1 for each edge {u, v} ∈ E(G). The backbone chromatic number BBC(G,H) is the smallest integer k such that there exists a backbone coloring with maxv∈V (G) c(v) = k. In this paper, we present the algorithm for the backbone coloring of split graphs with matching backbone.

Optimal bounds for the colored Tverberg problem

Pavle V. M. Blagojević, Benjamin Matschke, Günter M. Ziegler (2015)

Journal of the European Mathematical Society

We prove a “Tverberg type” multiple intersection theorem. It strengthens the prime case of the original Tverberg theorem from 1966, as well as the topological Tverberg theorem of Bárány et al. (1980), by adding color constraints. It also provides an improved bound for the (topological) colored Tverberg problem of Bárány & Larman (1992) that is tight in the prime case and asymptotically optimal in the general case. The proof is based on relative equivariant obstruction theory.

Optimal edge ranking of complete bipartite graphs in polynomial time

Ruo-Wei Hung (2006)

Discussiones Mathematicae Graph Theory

An edge ranking of a graph is a labeling of edges using positive integers such that all paths connecting two edges with the same label visit an intermediate edge with a higher label. An edge ranking of a graph is optimal if the number of labels used is minimum among all edge rankings. As the problem of finding optimal edge rankings for general graphs is NP-hard [12], it is interesting to concentrate on special classes of graphs and find optimal edge rankings for them efficiently. Apart from trees...

Optimal Locating-Total Dominating Sets in Strips of Height 3

Ville Junnila (2015)

Discussiones Mathematicae Graph Theory

A set C of vertices in a graph G = (V,E) is total dominating in G if all vertices of V are adjacent to a vertex of C. Furthermore, if a total dominating set C in G has the additional property that for any distinct vertices u, v ∈ V C the subsets formed by the vertices of C respectively adjacent to u and v are different, then we say that C is a locating-total dominating set in G. Previously, locating-total dominating sets in strips have been studied by Henning and Jafari Rad (2012). In particular,...

Optimal matrices of partitions and an application to Souslin trees

Gido Scharfenberger-Fabian (2010)

Fundamenta Mathematicae

The basic result of this note is a statement about the existence of families of partitions of the set of natural numbers with some useful properties, the n-optimal matrices of partitions. We use this to improve a decomposition result for strongly homogeneous Souslin trees. The latter is in turn applied to separate strong notions of rigidity of Souslin trees, thereby answering a considerable portion of a question of Fuchs and Hamkins.

Currently displaying 1261 – 1280 of 1336