For each vertex v of a graph G, if there exists a list of k colors, L(v), such that there is a unique proper coloring for G from this collection of lists, then G is called a uniquely k-list colorable graph. Ghebleh and Mahmoodian characterized uniquely 3-list colorable complete multipartite graphs except for nine graphs: $K_{2,2,r}$ r ∈ 4,5,6,7,8, $K_{2,3,4}$, $K_{1*4,4}$, $K_{1*4,5}$, $K_{1*5,4}$. Also, they conjectured that the nine graphs are not U3LC graphs. After that, except for $K_{2,2,r}$ r ∈ 4,5,6,7,8, the others have been proved not...

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...

We study the generalized $k$-connectivity ${\kappa }_k\left(G\right)$ as introduced by Hager in 1985, as well as the more recently introduced generalized $k$-edge-connectivity ${\lambda }_k\left(G\right)$. We determine the exact value of ${\kappa }_k\left(G\right)$ and ${\lambda }_k\left(G\right)$ for the line graphs and total graphs of trees, unicyclic graphs, and also for complete graphs for the case $k=3$.

In 1968 Erdős and Hajnal introduced shift graphs as graphs whose vertices are the k-element subsets of [n] = 1,...,n (or of an infinite cardinal κ ) and with two k-sets $A=a₁,...,a_k$ and $B=b₁,...,b_k$ joined if $a₁<a₂=b₁<a₃=b₂<\cdots <a_k=b_{k-1}<b_k$. They determined the chromatic number of these graphs. In this paper we extend this definition and study the chromatic number of graphs defined similarly for other types of mutual position with respect to the underlying ordering. As a consequence of our result, we show the existence of a graph with...

We describe two constructions of (very) dense graphs which are edge disjoint unions of large induced matchings. The first construction exhibits graphs on $N$ vertices with $\left(\frac{N}{2}\right)-o\left(N^2\right)$ edges, which can be decomposed into pairwise disjoint induced matchings, each of size $N^{1-o\left(1\right)}$. The second construction provides a covering of all edges of the complete graph $K_N$ by two graphs, each being the edge disjoint union of at most $N^{2-\delta }$ induced matchings, where $\delta >0,076$. This disproves (in a strong form) a conjecture of Meshulam,...

The paired domination number ${\gamma }_{pr}\left(G\right)$ of a graph G is the smallest cardinality of a dominating set S of G such that ⟨S⟩ has a perfect matching. The generalized prisms πG of G are the graphs obtained by joining the vertices of two disjoint copies of G by |V(G)| independent edges. We provide characterizations of the following three classes of graphs: ${\gamma }_{pr}\left(\pi G\right)=2{\gamma }_{pr}\left(G\right)$ for all πG; ${\gamma }_{pr}\left(K₂☐G\right)=2{\gamma }_{pr}\left(G\right)$; ${\gamma }_{pr}\left(K₂☐G\right)={\gamma }_{pr}\left(G\right)$.

A Roman dominating function on a graph G is a function f:V(G) → 0,1,2 satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The weight of a Roman dominating function is the value $f\left(V\left(G\right)\right)={\sum }_{u\in V\left(G\right)}f\left(u\right)$. The Roman domination number, ${\gamma }_R\left(G\right)$, of G is the minimum weight of a Roman dominating function on G. In this paper, we define the Roman bondage $b_R\left(G\right)$ of a graph G with maximum degree at least two to be the minimum cardinality of all sets E’ ⊆ E(G)...

Let $K_{s,t}$ be the complete bipartite graph with partite sets $\{x_1,...,x_s\}$ and $\{y_1,...,y_t\}$. A split bipartite-graph on $(s+s^{\text{'}})+(t+t^{\text{'}})$ vertices, denoted by ${\mathrm{SB}}_{s+s^{\text{'}},t+t^{\text{'}}}$, is the graph obtained from $K_{s,t}$ by adding $s^{\text{'}}+t^{\text{'}}$ new vertices $x_{s+1},...,x_{s+s^{\text{'}}}$, $y_{t+1},...,y_{t+t^{\text{'}}}$ such that each of $x_{s+1},...,x_{s+s^{\text{'}}}$ is adjacent to each of $y_1,...,y_t$ and each of $y_{t+1},...,y_{t+t^{\text{'}}}$ is adjacent to each of $x_1,...,x_s$. Let $A$ and $B$ be nonincreasing lists of nonnegative integers, having lengths $m$ and $n$, respectively. The pair $(A;B)$ is potentially ${\mathrm{SB}}_{s+s^{\text{'}},t+t^{\text{'}}}$-bigraphic if there is a simple bipartite graph containing ${\mathrm{SB}}_{s+s^{\text{'}},t+t^{\text{'}}}$ (with $s+s^{\text{'}}$ vertices $x_1,...,x_{s+s^{\text{'}}}$ in the part of size $m$...

A graph is called distance integral (or $D$-integral) if all eigenvalues of its distance matrix are integers. In their study of $D$-integral complete multipartite graphs, Yang and Wang (2015) posed two questions on the existence of such graphs. We resolve these questions and present some further results on $D$-integral complete multipartite graphs. We give the first known distance integral complete multipartite graphs $K_{p_1,p_2,p_3}$ with $p_1<p_2<p_3$, and $K_{p_1,p_2,p_3,p_4}$ with $p_1<p_2<p_3<p_4$, as well as the infinite classes of distance integral...

A graph G is said to be chromatic-choosable if ch(G) = χ(G). Ohba has conjectured that every graph G with 2χ(G)+1 or fewer vertices is chromatic-choosable. It is clear that Ohba’s conjecture is true if and only if it is true for complete multipartite graphs. In this paper we show that Ohba’s conjecture is true for complete multipartite graphs $K_{4,3*t,2*(k-2t-2),1*(t+1)}$ for all integers t ≥ 1 and k ≥ 2t+2, that is, $ch\left(K_{4,3*t,2*(k-2t-2),1*(t+1)}\right)=k$, which extends the results $ch\left(K_{4,3,2*(k-4),1*2}\right)=k$ given by Shen et al. (Discrete Math. 308 (2008) 136-143), and $ch\left(K_{4,3*2,2*(k-6),1*3}\right)=k$...

$G$-graphs are a type of graphs associated to groups, which were proposed by A. Bretto and A. Faisant (2005). In this paper, we first give some theorems regarding $G$-graphs. Then we introduce the notion of rough $G$-graphs and investigate some important properties of these graphs.

A $(0,2)$-graph is a connected graph, where each pair of vertices has either 0 or 2 common neighbours. These graphs constitute a subclass of $(0,\lambda )$-graphs introduced by Mulder in 1979. A rectagraph, well known in diagram geometry, is a triangle-free $(0,2)$-graph. $(0,2)$-graphs include hypercubes, folded cube graphs and some particular graphs such as icosahedral graph, Shrikhande graph, Klein graph, Gewirtz graph, etc. In this paper, we give some local properties of 4-cycles in $(0,\lambda )$-graphs and more specifically...

Let be a set of graphs and for a graph G let ${\alpha }_{}\left(G\right)$ and $\alpha {*}_{}\left(G\right)$ denote the maximum order of an induced subgraph of G which does not contain a graph in as a subgraph and which does not contain a graph in as an induced subgraph, respectively. Lower bounds on ${\alpha }_{}\left(G\right)$ and $\alpha {*}_{}\left(G\right)$ are presented.

In this paper, the chromaticity of K₃-gluings of two wheels is studied. For each even integer n ≥ 6 and each odd integer 3 ≤ q ≤ [n/2] all K₃-gluings of wheels $W_{q+2}$ and $W_{n-q+2}$ create an χ-equivalent class.

We consider certain class of second order nonlinear nonautonomous delay differential equations of the form $$a\left(t\right)x^{\text{'}\text{'}}+b\left(t\right)g(x,x^{\text{'}})+c\left(t\right)h\left(x(t-r)\right)m\left(x^{\text{'}}\right)=p(t,x,x^{\text{'}})$$ and $${\left(a\left(t\right)x^{\text{'}}\right)}^{\text{'}}+b\left(t\right)g(x,x^{\text{'}})+c\left(t\right)h\left(x(t-r)\right)m\left(x^{\text{'}}\right)=p(t,x,x^{\text{'}}),$$ where $a$, $b$, $c$, $g$, $h$, $m$ and $p$ are real valued functions which depend at most on the arguments displayed explicitly and $r$ is a positive constant. Different forms of the integral inequality method were used to investigate the boundedness of all solutions and their derivatives. Here, we do not require construction of the Lyapunov-Krasovski functional to establish our results....

In this paper, we study a model for the magnetization in thin ferromagnetic films. It comes as a variational problem for $S^1$-valued maps $m^{\text{'}}$ (the magnetization) of two variables $x^{\text{'}}$: $E_{\epsilon }\left(m^{\text{'}}\right)=\epsilon \int {|{\nabla }^{\text{'}}·m^{\text{'}}|}^{2}d{x}^{\text{'}}+\frac{1}{2}\int {\left||{\nabla }^{\text{'}}{|}^{-1/2}{\nabla }^{\text{'}}·m^{\text{'}}\right|}^{2}d{x}^{\text{'}}$. We are interested in the behavior of minimizers as $\epsilon \to 0$. They are expected to be $S^1$-valued maps $m^{\text{'}}$ of vanishing distributional divergence ${\nabla }^{\text{'}}·m^{\text{'}}=0$, so that appropriate boundary conditions enforce line discontinuities. For finite $\epsilon >0$, these line discontinuities are approximated by smooth transition layers, the so-called Néel...