A nonincreasing sequence $\pi =(d_1,...,d_n)$ of nonnegative integers is a graphic sequence if it is realizable by a simple graph $G$ on $n$ vertices. In this case, $G$ is referred to as a realization of $\pi$. Given two graphs $G_1$ and $G_2$, A. Busch et al. (2014) introduced the potential-Ramsey number of $G_1$ and $G_2$, denoted by $r_{\mathrm{pot}}(G_1,G_2)$, as the smallest nonnegative integer $m$ such that for every $m$-term graphic sequence $\pi$, there is a realization $G$ of $\pi$ with $G_1\subseteq G$ or with $G_2\subseteq \overline{G}$, where $\overline{G}$ is the complement of $G$. For $t\ge 2$ and $0\le k\le \lfloor \frac{t}{2}\rfloor$, let $K_t^{-k}$ be the graph obtained...

For any two graphs F1 and F2, the graph Ramsey number r(F1, F2) is the smallest positive integer N with the property that every graph on at least N vertices contains F1 or its complement contains F2 as a subgraph. In this paper, we consider the Ramsey numbers for theta-complete graphs. We determine r(θn,Km) for m = 2, 3, 4 and n > m. More specifically, we establish that r(θn,Km) = (n − 1)(m − 1) + 1 for m = 3, 4 and n > m

Bondy and Erdős [2] have conjectured that the Ramsey number for three cycles Cₖ of odd length has value r(Cₖ,Cₖ,Cₖ) = 4k-3. We give a proof that r(C₇,C₇,C₇) = 25 without using any computer support.

Let $L(n,d)$ denote the minimum possible number of leaves in a tree of order $n$ and diameter $d.$ Lesniak (1975) gave the lower bound $B(n,d)=\lceil 2(n-1)/d\rceil$ for $L(n,d).$ When $d$ is even, $B(n,d)=L(n,d).$ But when $d$ is odd, $B(n,d)$ is smaller than $L(n,d)$ in general. For example, $B(21,3)=14$ while $L(21,3)=19.$ In this note, we determine $L(n,d)$ using new ideas. We also consider the converse problem and determine the minimum possible diameter of a tree with given order and number of leaves.

A degree monotone path in a graph G is a path P such that the sequence of degrees of the vertices in the order in which they appear on P is monotonic. The length (number of vertices) of the longest degree monotone path in G is denoted by mp(G). This parameter, inspired by the well-known Erdős- Szekeres theorem, has been studied by the authors in two earlier papers. Here we consider a saturation problem for the parameter mp(G). We call G saturated if, for every edge e added to G, mp(G + e) > mp(G),...

The Wiener index W(G) of a connected graph G, introduced by Wiener in 1947, is defined as W(G) = ∑u,v∈V(G) d(u, v) where dG(u, v) is the distance between vertices u and v of G. The Steiner distance in a graph, introduced by Chartrand et al. in 1989, is a natural generalization of the concept of classical graph distance. For a connected graph G of order at least 2 and S ⊆ V (G), the Steiner distance d(S) of the vertices of S is the minimum size of a connected subgraph whose vertex set is S. We now...

If a graph G has a drawing in the plane in such a way that every two crossings are independent, then we call G a plane graph with independent crossings or IC-planar graph for short. In this paper, the structure of IC-planar graphs with minimum degree at least two or three is studied. By applying their structural results, we prove that the edge chromatic number of G is Δ if Δ ≥ 8, the list edge (resp. list total) chromatic number of G is Δ (resp. Δ + 1) if Δ ≥ 14 and the linear arboricity of G is...

We prove a structure theorem asserting that each superflat graph is tree-decomposable in a very nice way. As a consequence we fully determine the spectrum functions of theories of superflat graphs.

We give the Turán number ex (n, 2P5) for all positive integers n, improving one of the results of Bushaw and Kettle [Turán numbers of multiple paths and equibipartite forests, Combininatorics, Probability and Computing, 20 (2011) 837-853]. In particular we prove that ex (n, 2P5) = 3n−5 for n ≥ 18.

Let ex (n,G) denote the maximum number of edges in a graph on n vertices which does not contain G as a subgraph. Let Pi denote a path consisting of i vertices and let mPi denote m disjoint copies of Pi. In this paper we count ex(n, 3P4)

We discuss how to find the well-covered dimension of a graph that is the Cartesian product of paths, cycles, complete graphs, and other simple graphs. Also, a bound for the well-covered dimension of Kn × G is found, provided that G has a largest greedy independent decomposition of length c < n. Formulae to find the well-covered dimension of graphs obtained by vertex blowups on a known graph, and to the lexicographic product of two known graphs are also given.