The join of two graphs $G$ and $H$ is a graph formed from disjoint copies of $G$ and $H$ by connecting each vertex of $G$ to each vertex of $H$. We determine the flow number of the resulting graph. More precisely, we prove that the join of two graphs admits a nowhere-zero $3$-flow except for a few classes of graphs: a single vertex joined with a graph containing an isolated vertex or an odd circuit tree component, a single edge joined with a graph containing only isolated edges, a single edge plus an isolated...

One interesting example of a discrete mathematical model used in biology is a food web. The first biology courses in high school and in college present the fundamental nature of a food web, one that is understandable by students at all levels. But food webs as part of a larger system are often not addressed. This paper presents materials that can be used in undergraduate classes in biology (and mathematics) and provides students with the opportunity...

A consecutive colouring of a graph is a proper edge colouring with posi- tive integers in which the colours of edges incident with each vertex form an interval of integers. The idea of this colouring was introduced in 1987 by Asratian and Kamalian under the name of interval colouring. Sevast- janov showed that the corresponding decision problem is NP-complete even restricted to the class of bipartite graphs. We focus our attention on the class of consecutively colourable graphs whose all induced...

A graph G is said to be 1-tough if for every vertex cut S of G, the number of components of G − S does not exceed |S|. Being 1-tough is an obvious necessary condition for a graph to be hamiltonian, but it is not sufficient in general. We study the problem of characterizing all graphs H such that every 1-tough H-free graph is hamiltonian. We almost obtain a complete solution to this problem, leaving H = K1 ∪ P4 as the only open case.

In [2], Brousek characterizes all triples of graphs, G₁, G₂, G₃, with $G_i=K_{1,3}$ for some i = 1, 2, or 3, such that all G₁G₂G₃-free graphs contain a hamiltonian cycle. In [6], Faudree, Gould, Jacobson and Lesniak consider the problem of finding triples of graphs G₁, G₂, G₃, none of which is a $K_{1,s}$, s ≥ 3 such that G₁, G₂, G₃-free graphs of sufficiently large order contain a hamiltonian cycle. In this paper, a characterization will be given of all triples G₁, G₂, G₃ with none being $K_{1,3}$, such that all G₁G₂G₃-free...

The Erdős-Faber-Lovász conjecture is the statement that every graph that is the union of n cliques of size n intersecting pairwise in at most one vertex has chromatic number n. Kahn and Seymour proved a fractional version of this conjecture, where the chromatic number is replaced by the fractional chromatic number. In this note we investigate similar fractional relaxations of the Erdős-Faber-Lovász conjecture, involving variations of the fractional chromatic number. We exhibit some relaxations that...

Let G = (V,E) be a connected graph and let k be a positive integer with k ≤ rad(G). A subset D ⊆ V is called a distance k-dominating set of G if for every v ∈ V - D, there exists a vertex u ∈ D such that d(u,v) ≤ k. In this paper we study the fractional version of distance k-domination and related parameters.

Mynhardt has conjectured that if G is a graph such that γ(G) = γ(πG) for all generalized prisms πG then G is edgeless. The fractional analogue of this conjecture is established and proved by showing that, if G is a graph with edges, then ${\gamma }_f\left(G\times K₂\right)>{\gamma }_f\left(G\right)$.

Let G = (V,E) be a graph. A function g:V → [0,1] is called a global dominating function (GDF) of G, if for every v ∈ V, $g\left(N\left[v\right]\right)={\sum }_{u\in N\left[v\right]}g\left(u\right)\ge 1$ and $g\left(\overline{N\left(v\right)}\right)={\sum }_{u\notin N\left(v\right)}g\left(u\right)\ge 1$. A GDF g of a graph G is called minimal (MGDF) if for all functions f:V → [0,1] such that f ≤ g and f(v) ≠ g(v) for at least one v ∈ V, f is not a GDF. The fractional global domination number ${\gamma }_{fg}\left(G\right)$ is defined as follows: ${\gamma }_{fg}\left(G\right)$ = min|g|:g is an MGDF of G where $\left|g\right|={\sum }_{v\in V}g\left(v\right)$. In this paper we initiate a study of this parameter.

Let r, s ∈ N, r ≥ s, and P and Q be two additive and hereditary graph properties. A (P,Q)-total (r, s)-coloring of a graph G = (V,E) is a coloring of the vertices and edges of G by s-element subsets of Zr such that for each color i, 0 ≤ i ≤ r − 1, the vertices colored by subsets containing i induce a subgraph of G with property P, the edges colored by subsets containing i induce a subgraph of G with property Q, and color sets of incident vertices and edges are disjoint. The fractional (P,Q)-total...

An additive hereditary property of graphs is a class of simple graphs which is closed under unions, subgraphs and isomorphism. Let [...] be an additive hereditary property of graphs. A [...] -edge-coloring of a simple graph is an edge coloring in which the edges colored with the same color induce a subgraph of property [...] . In this paper we present some results on fractional [...] -edge-colorings. We determine the fractional [...] -edge chromatic number for matroidal properties of graphs.