A Class of Edge Critical 4-Chromatic Graphs

We consider several constructions of edge critical 4-chromatic graphs which can be written as the union of a bipartite graph and a matching. In particular we construct such a graph G with each of the following properties: G can be contracted to a given critical 4-chromatic graph; for each n ≥ 7, G has n vertices and three matching edges (it is also shown that such graphs must have at least \({{8n} \over 5}\) edges); G has arbitrary large girth.     

Domination in Bipartite Graphs and in Their Complements

The domatic numbers of a graph G and of its complement $\bar G$ were studied by J. E. Dunbar, T. W. Haynes and M. A. Henning. They suggested four open problems. We will solve the following ones: Characterize bipartite graphs G having $d\left( G \right) = d\left( {\bar G} \right)$ Further, we will present a partial solution to the problem: Is it true that if G is a graph satisfying $d\left( G \right) = d\left( {\bar G} \right)$ then $\gamma \left( G \right) = \gamma \left( {\bar G} \right)$ ? Finally, we prove an existence theorem concerning the total domatic number of a graph and of its complement     

Degree Sum Conditions for Cyclability in Bipartite Graphs

We denote by G[X, Y] a bipartite graph G with partite sets X and Y. Let d _G (v) be the degree of a vertex v in a graph G. For G[X, Y] and ${S \subseteq V(G),}$ we define ${\sigma_{1,1}(S):=\min\{d_G(x)+d_G(y) : (x,y) \in (X \cap S,Y) \cup (X, Y \cap S), xy \not\in E(G)\}}$ . Amar et al. (Opusc. Math. 29:345–364, 2009) obtained σ _1,1(S) condition for cyclability of balanced bipartite graphs. In this paper, we generalize the result as it includes the case of unbalanced bipartite graphs: if G[X, Y] is a 2-connected bipartite graph with |X| ≥ |Y| and ${S \subseteq V(G)}$ such that σ _1,1(S) ≥ |X| + 1, then either there exists a cycle containing S or ${|S \cap X| > |Y|}$ and there exists a cycle containing Y. This degree sum condition is sharp.     

Characterizations of Strength Extremal Graphs

With graphs considered as natural models for many network design problems, edge connectivity κ′(G) and maximum number of edge-disjoint spanning trees τ(G) of a graph G have been used as measures for reliability and strength in communication networks modeled as graph G (see Cunningham, in J ACM 32:549–561, 1985; Matula, in Proceedings of 28th Symposium Foundations of Computer Science, pp 249–251, 1987, among others). Mader (Math Ann 191:21–28, 1971) and Matula (J Appl Math 22:459–480, 1972) introduced the maximum subgraph edge connectivity \({\overline{\kappa'}(G) = {\rm max} \{\kappa'(H) : H {\rm is} \, {\rm a} \, {\rm subgraph} \, {\rm of} G \}}\) . Motivated by their applications in network design and by the established inequalities $$\overline{\kappa'}(G) \ge \kappa'(G) \ge \tau(G),$$ we present the following in this paper:

1. For each integer k > 0, a characterization for graphs G with the property that \({\overline{\kappa'}(G) \le k}\) but for any edge e not in G, \({\overline{\kappa'}(G + e) \ge k+1}\) .
2. For any integer n > 0, a characterization for graphs G with |V(G)| = n such that κ′(G) = τ(G) with |E(G)| minimized.

     

Degree Sum Conditions for Hamiltonicity on k-Partite Graphs

One of the earliest results about hamiltonian graphs was given by Dirac. He showed that if a graph G has order p and minimum degree at least \(\frac{p} {2}\) then G is hamiltonian. Moon and Moser showed that if G is a balanced bipartite graph (the two partite sets have the same order) with minimum degree more than \(\frac{p} {4}\) then G is hamiltonian. Recently their idea is generalized to k-partite graphs by Chen, Faudree, Gould, Jacobson, and Lesniak in terms of minimum degrees. In this paper, we generalize this result in terms of degree sum and the following result is obtained: Let G be a balanced k-partite graph with order kn. If for every pair of nonadjacent vertices u and v which are in different parts $$d(u) + d(v) > \left\{ {\begin{array}{*{20}c} {\left( {k - \frac{2} {{k + 1}}} \right)n} & {if k is odd} \\ {\left( {k - \frac{4} {{k + 2}}} \right)n} & {if k is even} \\ \end{array} } \right.,$$ then G is hamiltonian.     

Regularity of powers of bipartite graphs

Let G be a finite simple graph and I(G) denote the corresponding edge ideal. For all \(s \ge 1\), we obtain upper bounds for \({\text {reg}}(I(G)^s)\) for bipartite graphs. We then compare the properties of G and \(G'\), where \(G'\) is the graph associated with the polarization of the ideal \((I(G)^{s+1} : e_1\cdots e_s)\), where \(e_1,\cdots , e_s\) are edges of G. Using these results, we explicitly compute \({\text {reg}}(I(G)^s)\) for several subclasses of bipartite graphs.     

On the Edge Connectivity of Direct Products with Dense Graphs

Let ${\kappa^{\prime}(G)}$ be the edge connectivity of G and G × H the direct product of G and H. Let H be any graph with minimal degree ${\delta(H)>|V(H)|/2}$ . We prove that for any graph ${G, \kappa^{\prime}(G\times H)=\textup{min}\{2\kappa^{\prime}(G)|E(H)|,\delta(G)\delta(H)\}}$ . In addition, the structure of minimum edge cuts is described. As an application, we present a necessary and sufficient condition for G × K _n (n ≥ 3) to be super edge connected.     

Dominating Cycles and Forbidden Pairs Containing $$P_{5}$$

A cycle C in a graph G is dominating if every edge of G is incident with at least one vertex of C. For a set \(\mathcal {H}\) of connected graphs, a graph G is said to be \(\mathcal {H}\)-free if G does not contain any member of \(\mathcal {H}\) as an induced subgraph. When \(|\mathcal {H}| = 2, \mathcal {H}\) is called a forbidden pair. In this paper, we investigate the characterization of the class of the forbidden pairs guaranteeing the existence of a dominating cycle and show the following two results: (i) Every 2-connected \(\{P_{5}, K_{4}^{-}\}\)-free graph contains a longest cycle which is a dominating cycle. (ii) Every 2-connected \(\{P_{5}, W^{*}\}\)-free graph contains a longest cycle which is a dominating cycle. Here \(P_{5}\) is the path of order \(5, K_{4}^{-}\) is the graph obtained from the complete graph of order 4 by removing one edge, and \(W^{*}\) is the graph obtained from two triangles and an edge by identifying one vertex in each.     

The Chvátal–Erdös Condition for Group Connectivity in Graphs

Let G be a graph and A an abelian group with the identity element 0 and ${|A| \geq 4}$ . Let D be an orientation of G. The boundary of a function ${f: E(G) \rightarrow A}$ is the function ${\partial f: V(G) \rightarrow A}$ given by ${\partial f(v) = \sum_{e \in E^+(v)}f(e) - \sum_{e \in E^-(v)}f(e)}$ , where ${v \in V(G), E^+(v)}$ is the set of edges with tail at v and ${E^-(v)}$ is the set of edges with head at v. A graph G is A-connected if for every b: V(G) → A with ${\sum_{v \in V(G)} b(v) = 0}$ , there is a function ${f: E(G) \mapsto A-\{0\}}$ such that ${\partial f = b}$ . A graph G is A-reduced to G′ if G′ can be obtained from G by contracting A-connected subgraphs until no such subgraph left. Denote by ${\kappa^{\prime}(G)}$ and α(G) the edge connectivity and the independent number of G, respectively. In this paper, we prove that for a 2-edge-connected simple graph G, if ${\kappa^{\prime}(G) \geq \alpha(G)-1}$ , then G is A-connected or G can be A-reduced to one of the five specified graphs or G is one of the 13 specified graphs.     

Collapsible Graphs and Hamiltonicity of Line Graphs

Thomassen conjectured that every 4-connected line graph is Hamiltonian. Chen and Lai (Combinatorics and Graph Theory, vol 95, World Scientific, Singapore, pp 53–69; Conjecture 8.6 of 1995) conjectured that every 3-edge connected and essentially 6-edge connected graph is collapsible. Denote D ₃(G) the set of vertices of degree 3 of graph G. For ${e = uv \in E(G)}$ , define d(e) = d(u) + d(v) ? 2 the edge degree of e, and ${\xi(G) = \min\{d(e) : e \in E(G)\}}$ . Denote by λ ^m (G) the m-restricted edge-connectivity of G. In this paper, we prove that a 3-edge-connected graph with ${\xi(G)\geq7}$ , and ${\lambda^3(G)\geq7}$ is collapsible; a 3-edge-connected simple graph with ${\xi(G)\geq7}$ , and ${\lambda^3(G)\geq6}$ is collapsible; a 3-edge-connected graph with ${\xi(G)\geq6}$ , ${\lambda^2(G)\geq4}$ , and ${\lambda^3(G)\geq6}$ with at most 24 vertices of degree 3 is collapsible; a 3-edge-connected simple graph with ${\xi(G)\geq6}$ , and ${\lambda^3(G)\geq5}$ with at most 24 vertices of degree 3 is collapsible; a 3-edge-connected graph with ${\xi(G)\geq5}$ , and ${\lambda^2(G)\geq4}$ with at most 9 vertices of degree 3 is collapsible. As a corollary, we show that a 4-connected line graph L(G) with minimum degree at least 5 and ${|D_3(G)|\leq9}$ is Hamiltonian.     

Upper Bounds on the Paired Domination Subdivision Number of a Graph

A paired dominating set of a graph G with no isolated vertex is a dominating set S of vertices such that the subgraph induced by S in G has a perfect matching. The paired domination number of G, denoted by γ _pr(G), is the minimum cardinality of a paired dominating set of G. The paired domination subdivision number ${{\rm sd}_{\gamma _{\rm pr}}(G)}$ is the minimum number of edges to be subdivided (each edge of G can be subdivided at most once) in order to increase the paired domination number. In this paper, we show that if G is a connected graph of order at least 4, then ${{\rm sd}_{\gamma _{\rm pr}}(G)\leq 2|V(G)|-5}$ . We also characterize trees T such that ${{\rm sd}_{\gamma _{\rm pr}}(T) \geq |V(T)| /2}$ .     

On Edge Cut of Graphs Leaving Components of Order at Least Five

An edge cut of a connected graph is 5-restricted if its removal leaves every component having order at least five. Graphs that contain 5-restricted edge cuts are characterized in this paper. As a result, it is shown that a connected graph G of order at least 13 contains 5-restricted edge cuts if and only if ${G \setminus v}$ contains a component of order at least five for every vertex v of graph G.     

The Hirsch Conjecture for the fractional stable set polytope

The edge formulation of the stable set problem is defined by two-variable constraints, one for each edge of a graph \(G\) , expressing the simple condition that two adjacent nodes cannot belong to a stable set. We study the fractional stable set polytope, i.e. the polytope defined by the linear relaxation of the edge formulation. Even if this polytope is a weak approximation of the stable set polytope, its simple geometrical structure provides deep theoretical insight as well as interesting algorithmic opportunities. Exploiting a graphic characterization of the bases, we first redefine pivots in terms of simple graphic operations, that turn a given basis into an adjacent one. These results lead us to prove that the combinatorial diameter of the fractional stable set polytope is at most the number of nodes of the given graph. As a corollary, the Hirsch bound holds for this class of polytopes.     

Neighborhood Unions for the Existence of Disjoint Chorded Cycles in Graphs

A chorded cycle is a cycle with at least one chord. We prove that if G is a simple graph with order n ≥ 4k and ${|N_G(x)\cup N_G(y)|\geq 4k+1}$ for each nonadjacent pair of vertices x and y, then G contains k vertex-disjoint chorded cycles. The degree condition is sharp in general.     

On Coprimality Graphs for Symmetric Groups

For G a group, X a subset of G and π a set of positive integers we define a graph ${\mathcal{C}_{\pi}(G,X)}$ whose vertex set is X with ${x,y \in X}$ joined by an edge provided x ≠ y and the order of xy is in π. Here we investigate ${\mathcal{C}_{\pi}(G,X)}$ when G is a finite symmetric group and X is a G-conjugacy class of elements of order p, p a prime.     

The Jumping Knight and Other (Super) Edge-Magic Constructions

Let G be a graph of order p and size q with loops allowed. A bijective function ${f:V(G)\cup E(G)\rightarrow \{i\}_{i=1}^{p+q}}$ is an edge-magic labeling of G if the sum ${f(u)+f(uv)+f(v)=k}$ is independent of the choice of the edge uv. The constant k is called either the valence, the magic weight or the magic sum of the labeling f. If a graph admits an edge-magic labeling, then it is called an edge-magic graph. Furthermore, if the function f meets the extra condition that ${f(V(G))=\{i\}_{i=1}^{p}}$ then f is called a super edge-magic labeling and G is called a super edge-magic graph. A digraph D admits a labeling, namely l, if its underlying graph, und(D) admits l. In this paper, we introduce a new construction of super edge-magic labelings which are related to the classical jump of the knight on the chess game. We also use super edge-magic labelings of digraphs together with a generalization of the Kronecker product to get edge-magic labelings of some families of graphs.     

Graphs with Average Degree Smaller Than {\frac {30}{11}} Burn Slowly

In this paper, we consider the following firefighter problem on a finite graph G =  (V, E). Suppose that a fire breaks out at a given vertex ${v \in V}$ . In each subsequent time unit, a firefighter protects one vertex which is not yet on fire, and then the fire spreads to all unprotected neighbours of the vertices on fire. The objective of the firefighter is to save as many vertices as possible. The surviving rate ${\rho(G)}$ of G is defined as the expected percentage of vertices that can be saved when a fire breaks out at a random vertex of G. Let ε >  0. We show that any graph G on n vertices with at most ${(\frac {15}{11} - \varepsilon)n}$ edges can be well protected, that is, ${\rho(G) > \frac {\varepsilon}{60} > 0}$ . Moreover, a construction of a random graph is proposed to show that the constant ${\frac {15}{11}}$ cannot be improved.     

Invariant random graphs with iid degrees in a general geography

Let D be a non-negative integer-valued random variable and let G = (V, E) be an infinite transitive finite-degree graph. Continuing the work of Deijfen and Meester (Adv Appl Probab 38:287–298) and Deijfen and Jonasson (Electron Comm Probab 11:336–346), we seek an Aut(G)-invariant random graph model with V as vertex set, iid degrees distributed as D and finite mean connections (i.e., the sum of the edge lengths in the graph metric of G of a given vertex has finite expectation). It is shown that if G has either polynomial growth or rapid growth, then such a random graph model exists if and only if ${\mathbb{E}[D\,R(D)] < \infty}$ . Here R(n) is the smallest possible radius of a combinatorial ball containing more than n vertices. With rapid growth we mean that the number of vertices in a ball of radius n is of at least order exp(n ^c ) for some c > 0. All known transitive graphs have either polynomial or rapid growth. It is believed that no other growth rates are possible. When G has rapid growth, the result holds also when the degrees form an arbitrary invariant process. A counter-example shows that this is not the case when G grows polynomially. For this case, we provide other, quite sharp, conditions under which the stronger statement does and does not hold respectively. Our work simplifies and generalizes the results for ${G\,=\,\mathbb {Z}}$ in [4] and proves, e.g., that with ${G\,=\,\mathbb {Z}^d}$ , there exists an invariant model with finite mean connections if and only if ${\mathbb {E}[D^{(d+1)/d}] < \infty}$ . When G has exponential growth, e.g., when G is a regular tree, the condition becomes ${\mathbb {E}[D\,\log\,D] < \infty}$ .