Search

We extend a result of Griggs and Yeh about the maximum possible value of the L(2, 1)-labeling number of a graph in terms of its maximum degree to oriented graphs. We consider the problem both in the usual definition of the oriented L(2, 1)-labeling number and in some variants we introduce.

In 1979, Hakimi and Schmeichel considered the problem of maximizing the number of cycles of a given length in an n $n$‐vertex planar graph. They precisely determined the maximum number of triangles and four‐cycles and presented a conjecture for the maximum number of pentagons. In this work, we confirm their conjecture. Even more, we characterize the n $n$‐vertex, planar graphs with the maximum number of pentagons. [ABSTRACT FROM AUTHOR]

Let F be a nonempty family of graphs. A graph is called F -free if it contains no graph from F as a subgraph. For a positive integer , the planar Turán number of F, denoted by exp (, F), is the maximum number of edges in an -vertex F -free planar graph. Let Θ be the family of Theta graphs on ≥ 4 vertices, that is, graphs obtained by joining a pair of non-consecutive of a -cycle with an edge. Lan, Shi and Song determined an upper bound exp (, Θ6) ≤ 18/7−36/7, but for large , they did not verify that the bound is sharp. In this paper, we improve their bound by proving exp (, Θ6) ≤ 18/−48/7 and then we demonstrate the existence of infinitely many positive integer and an -vertex Θ6-free planar graph attaining the bound. [ABSTRACT FROM AUTHOR]

A tree T on 2n vertices is called set-sequential if the elements in V (T) ∪ E(T) can be labeled with distinct nonzero (n + 1)-dimensional 01-vectors such that the vector labeling each edge is the component-wise sum modulo 2 of the labels of the endpoints. It has been conjectured that all trees on 2n vertices with only odd degree are set-sequential (the "Odd Tree Conjecture"), and in this paper, we present progress toward that conjecture. We show that certain kinds of caterpillars (with restrictions on the degrees of the vertices, but no restrictions on the diameter) are set-sequential. Additionally, we introduce some constructions of new set-sequential graphs from smaller set-sequential bipartite graphs (not necessarily odd trees). We also make a conjecture about pairings of the elements of Fn2 in a particular way; in the process, we provide a substantial clarification of a proof of a theorem that partitions Fn2 from a paper [P.N. Balister, E. Győri and R.H. Schelp, Coloring vertices and edges of a graph by nonempty subsets of a set, European J. Combin. 32 (2011) 533-537]. Finally, we put forward a result on bipartite graphs that is a modification of a theorem in the aforementioned paper. [ABSTRACT FROM AUTHOR]

In 1952, Dirac proved that every 2‐connected n$n$‐vertex graph with the minimum degree k+1$k+1$ contains a cycle of length at least min{n,2(k+1)}$\min \lbrace n, 2(k+1)\rbrace$. Here we obtain a stability version of this result by characterizing those graphs with minimum degree k$k$ and circumference at most 2k+1$2k+1$. We present applications of the above‐stated result by obtaining generalized Turán numbers. In particular, for all ℓ⩾5$\ell \geqslant 5$ we determine how many copies of a five‐cycle as well as four‐cycle are necessary to guarantee that the graph has a circumference larger than ℓ$\ell$. In addition, we give a new proof of Luo's theorem for cliques using our stability result. [ABSTRACT FROM AUTHOR]