Bipartite permutation graphs have several nice characterizations in terms of vertex ordering. Besides, as AT-free graphs, they have a linear structure in the sense that any connected bipartite permutation graph has a dominating path. In the present paper, we elaborate the linear structure of bipartite permutation graphs by showing that any connected graph in the class can be stretched into a “path” with “edges” being chain graphs. A particular consequence from the obtained characterization is that the clique-width of bipartite permutation graphs is unbounded, which refines a recent result of Golumbic and Rotics for permutation graphs.

A known result due to Matthews and Sunner is that every \(2\)-connected claw-free graph on \(n\) vertices contains a cycle of length at least \(\min\{2\delta+4,n\}\), and is Hamiltonian if \(n \leq 3\delta+2\). In this paper, we show that every \(2\)-connected claw-free graph on \(n\) vertices which does not belong to one of three classes of exceptional graphs contains a cycle of length at least \(\min\{4\delta-2,n\}\), hereby generalizing several known results. Moreover, the bound \(4\delta-2\) is almost best possible.

A graph or a digraph \(G\) is called super-edge-connected or super-\(\lambda\), if every minimum edge cut consists of edges adjacent to or from a vertex of minimum degree. Clearly, if \(G\) is super-\(\lambda\), then \(\lambda(G) = \delta(G)\), where \(\delta(G)\) is the minimum degree and \(\lambda(G)\) is the edge-connectivity of \(G\).

In this paper, degree sequence conditions for graphs and digraphs as well as for bipartite graphs and digraphs to be super-\(\lambda\) are presented.

Given integers \(k \geq 2\) and \(n \geq k\), let \(e(n, k)\) denote the maximum possible number of edges in an \(m\)-vertex graph which has no \(k\)-connected subgraph. It is immediate that \(e(n, 2) = n – 1\). Mader [2] conjectured that for every \(k \leq 2\), if \(n\) is sufficiently large then \(c(n, k) \leq (1.5k-2)(n – k + 1),\) where equality holds whenever \(k – 1\) divides \(n\). In this note we prove that when \(n\) is sufficiently large then \(e(n, k) \leq \frac{193}{120}(k – 1)(n – k + 1) < 1.61(k – 1)(n – k + 1),\) thereby coming rather close to the conjectured bound.

In this paper, we give a few applications of combinatorial design theory to a few problems in extremal graph theory. Using known results in combinatorial design theory, we have unified, simplified, and extended results on a few problems.

Let \(G\) be a simple graph with vertex set \(V\) and edge set \(E\). A vertex labeling \(\overline{f}: V \to \{0,1\}\) induces an edge labeling \(\overline{f}: E \to \{0,1\}\) defined by \(f(uv) = |f(u) – f(v)|\). Let \(v_f(0),v_f(1)\) denote the number of vertices \(v\) with \(f(v) = 0\) and \(f(v) = 1\) respectively. Let \(e_f(0),e_f(1)\) be similarly defined. A graph is said to be cordial if there exists a vertex labeling \(f\) such that \(|v_f(0) – vf(1)| \leq 1\) and \(|e_f(0) – e_f(1)| \leq 1\).

A \(t\)-uniform homeomorph \(P_t(G)\) of \(G\) is the graph obtained by replacing all edges of \(G\) by vertex disjoint paths of length \(t\). In this paper we show that (1)\(P_t(K_{2n})\) is cordial for all \(t \geq 2\).(2) \(P_t(K_{2n+1})\) is cordial if and only iff (a) \(t \equiv 0 \pmod{4}\), or(b) \(t\) is odd and \(n\) is not \(\equiv 2 \pmod{4}\), or (c) \(t \equiv 2 \pmod{4}\) and \(n\) is even.

For any positive integer \(k\), a graph \(G = (V, E)\) is said to be \(\mathbb{Z}_k\)-magic if there exists a labeling \(l: E(G) \to \mathbb{Z}_k – \{0\}\) such that the induced vertex set labeling \(l^+: V(G) \to \mathbb{Z}_k\) defined by

\[l^+(v) = \sum\{l(uv): uv \in E(G)\}\]

is a constant map. For a given graph \(G\), the set of all \(h \in \mathbb{Z_+}\) for which \(G\) is \(\mathbb{Z}_h\)-magic is called the integer-magic spectrum of \(G\) and is denoted by \(IM(G)\). In this paper, we will determine the integer-magic spectra of the graphs which are formed by the amalgamation of stars and cycles. In particular, we will provide examples of graphs that for a given \(n > 2\), they are not \(h\)-magic for all values of \(2 \leq k \leq n\).

In this paper, various transformations of the set of closed meanders are introduced. Some of these are used in order to partition the above set and to find a representative of each class. Furthermore, each closed meander is separated into shorter ones.

We develop a combinatorial model of paperfolding for the purposes of enumeration. A planar embedding of a graph is called a crease pattern if it represents the crease lines needed to fold a piece of paper into something. A flat fold is a crease pattern which lies flat when folded, i.e., can be pressed in a book without crumpling. Given a crease pattern \(C = (V, E)\), a mountain-valley (MV) assignment is a function \(f : E \to \{M, V\}\) which indicates which crease lines are convex and which are concave, respectively. A MV assignment is valid if it doesn’t force the paper to self-intersect when folded. We examine the problem of counting the number of valid MV assignments for a given crease pattern. In particular, we develop recursive functions that count the number of valid MV assignments for flat vertex folds, crease patterns with only one vertex in the interior of the paper. We also provide examples, especially those of Justin, that illustrate the difficulty of the general multivertex case.

An asteroidal triple is an independent set of three vertices in a graph such that every two of them are joined by a path avoiding the closed neighborhood of the third. Graphs without asteroidal triples are called AT-free graphs. In this paper, we show that every AT-free graph admits a vertex ordering that we call a \(2\)-cocomparability ordering. The new suggested ordering generalizes the cocomparability ordering achievable for cocomparability graphs. According to the property of this ordering, we show that every proper power \(G^k\) (\(k \geq 2\)) of an AT-free graph \(G\) is a cocomparability graph. Moreover, we demonstrate that our results can be exploited for algorithmic purposes on AT-free graphs.