As a general case of molecular graphs of benzenoid hydrocarbons, we study plane bipartite graphs with Kekulé structures (1-factors). A bipartite graph G is called elementary if G is connected and every edge belongs to a 1-factor of G. Some properties of the minimal and the maximal 1-factor of a plane elementary graph are given. A peripheral face f of a plane elementary graph is reducible, if the removal of the internal vertices and edges of the path that is the intersection of...

A complete 4-partite graph $K_{m₁,m₂,m₃,m₄}$ is called d-halvable if it can be decomposed into two isomorphic factors of diameter d. In the class of graphs $K_{m₁,m₂,m₃,m₄}$ with at most one odd part all d-halvable graphs are known. In the class of biregular graphs $K_{m₁,m₂,m₃,m₄}$ with four odd parts (i.e., the graphs $K_{m,m,m,n}$ and $K_{m,m,n,n}$) all d-halvable graphs are known as well, except for the graphs $K_{m,m,n,n}$ when d = 2 and n ≠ m. We prove that such graphs are 2-halvable iff n,m ≥ 3. We also determine a new class of non-halvable graphs $K_{m₁,m₂,m₃,m₄}$ with three or four different...

We characterize the class [...] L32 $L_3^2$ of intersection graphs of hypergraphs with rank at most 3 and multiplicity at most 2 by means of a finite list of forbidden induced subgraphs in the class of threshold graphs. We also give an O(n)-time algorithm for the recognition of graphs from [...] L32 $L_3^2$ in the class of threshold graphs, where n is the number of vertices of a tested graph.

The split graph $K_r+\overline{K_s}$ on $r+s$ vertices is denoted by $S_{r,s}$. A non-increasing sequence $\pi =(d_1,d_2,...,d_n)$ of nonnegative integers is said to be potentially $S_{r,s}$-graphic if there exists a realization of $\pi$ containing $S_{r,s}$ as a subgraph. In this paper, we obtain a Havel-Hakimi type procedure and a simple sufficient condition for $\pi$ to be potentially $S_{r,s}$-graphic. They are extensions of two theorems due to A. R. Rao (The clique number of a graph with given degree sequence, Graph Theory, Proc. Symp., Calcutta 1976, ISI Lect. Notes Series...

For a connected graph $G=(V,E)$ and a set $S\subseteq V\left(G\right)$ with at least two vertices, an $S$-Steiner tree is a subgraph $T=(V^{\text{'}},E^{\text{'}})$ of $G$ that is a tree with $S\subseteq V^{\text{'}}$. If the degree of each vertex of $S$ in $T$ is equal to 1, then $T$ is called a pendant $S$-Steiner tree. Two $S$-Steiner trees are internally disjoint if they share no vertices other than $S$ and have no edges in common. For $S\subseteq V\left(G\right)$ and $\left|S\right|\ge 2$, the pendant tree-connectivity ${\tau }_G\left(S\right)$ is the maximum number of internally disjoint pendant $S$-Steiner trees in $G$, and for $k\ge 2$, the $k$-pendant tree-connectivity ${\tau }_k\left(G\right)$...

Let G = (V, E) be a simple graph of order n and i be an integer with i ≥ 1. The set X i ⊆ V(G) is called an i-packing if each two distinct vertices in X i are more than i apart. A packing colouring of G is a partition X = {X 1, X 2, …, X k} of V(G) such that each colour class X i is an i-packing. The minimum order k of a packing colouring is called the packing chromatic number of G, denoted by χρ(G). In this paper we show, using a theoretical proof, that if q = 4t, for some integer t ≥ 3, then 9...

The following result is proved: Let $G$ be a connected graph of order $geq4$. Then for every matching $M$ in $G^4$ there exists a hamiltonian cycle $C$ of $G^4$ such that $E\left(C\right)\bigcap M=0$.

A polyomino graph P is a connected finite subgraph of the infinite plane grid such that each finite face is surrounded by a regular square of side length one and each edge belongs to at least one square. A dimer covering of P corresponds to a perfect matching. Different dimer coverings can interact via an alternating cycle (or square) with respect to them. A set of disjoint squares of P is a resonant set if P has a perfect matching M so that each one of those squares is M-alternating. In this paper,...

Let G be a graph of order n, and let a and b be two integers with 1 ≤ a ≤ b. Let h : E(G) → [0, 1] be a function. If a ≤ ∑e∋x h(e) ≤ b holds for any x ∈ V (G), then we call G[Fh] a fractional [a, b]-factor of G with indicator function h, where Fh = {e ∈ E(G) : h(e) > 0}. A graph G is fractional independent-set-deletable [a, b]-factor-critical (in short, fractional ID-[a, b]- factor-critical) if G − I has a fractional [a, b]-factor for every independent set I of G. In this paper, it is proved...