In 1960, Dirac put forward the conjecture that r-connected 4-critical graphs exist for every r ≥ 3. In 1989, Erdös conjectured that for every r ≥ 3 there exist r-regular 4-critical graphs. A method for finding r-regular 4-critical graphs and the numbers of such graphs for r ≤ 10 have been reported in [6,7]. Results of a computer search for graphs of degree r = 12,14,16 are presented. All the graphs found are both r-regular and r-connected.

For a nontrivial connected graph $F$, the $F$-degree of a vertex $v$ in a graph $G$ is the number of copies of $F$ in $G$ containing $v$. A graph $G$ is $F$-continuous (or $F$-degree continuous) if the $F$-degrees of every two adjacent vertices of $G$ differ by at most 1. All $P_3$-continuous graphs are determined. It is observed that if $G$ is a nontrivial connected graph that is $F$-continuous for all nontrivial connected graphs $F$, then either $G$ is regular or $G$ is a path. In the case of a 2-connected graph $F$, however, there...

In this paper, we consider self-mappings defined on a metric space endowed with a finite number of graphs. Under certain conditions imposed on the graphs, we establish a new fixed point theorem for such mappings. The obtained result extends, generalizes and improves many existing contributions in the literature including standard fixed point theorems, fixed point theorems on a metric space endowed with a partial order and fixed point theorems for cyclic mappings.

The generalized $k$-connectivity ${\kappa }_k\left(G\right)$ of a graph $G$ was introduced by Chartrand et al. in 1984. As a natural counterpart of this concept, Li et al. in 2011 introduced the concept of generalized $k$-edge-connectivity which is defined as ${\lambda }_k\left(G\right)=min\{\lambda \left(S\right):S\subseteq V\left(G\right)$ and $\left|S\right|=k\}$, where $\lambda \left(S\right)$ denotes the maximum number $\ell$ of pairwise edge-disjoint trees $T_1,T_2,...,T_{\ell }$ in $G$ such that $S\subseteq V\left(T_i\right)$ for $1\le i\le \ell$. In this paper we prove that for any two connected graphs $G$ and $H$ we have ${\lambda }_3(G\square H)\ge {\lambda }_3\left(G\right)+{\lambda }_3\left(H\right)$, where $G\square H$ is the Cartesian product of $G$ and $H$. Moreover, the bound is sharp. We also obtain the...

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

Let $G$ be a graph. A vertex subversion strategy of $G$, say $S$, is a set of vertices in $G$ whose closed neighborhood is removed from $G$. The survival-subgraph is denoted by $G/S$. The Neighbor-Integrity of $G$, $\mathrm{N}I\left(G\right)$, is defined to be $\mathrm{N}I\left(G\right)={min}_{S\subseteq V\left(G\right)}\left\{\right|S|+c(G/S)\}$, where $S$ is any vertex subversion strategy of $G$, and $c(G/S)$ is the maximum order of the components of $G/S$. In this paper we give some results connecting the neighbor-integrity and binary graph operations.

The paper studies graphs in which each pair of vertices has exactly two common neighbours. It disproves a conjectury by P. Hliněný concerning these graphs.

The generalized k-connectivity κk(G) of a graph G, introduced by Hager in 1985, is a nice generalization of the classical connectivity. Recently, as a natural counterpart, we proposed the concept of generalized k-edge-connectivity λk(G). In this paper, graphs of order n such that [...] for even k are characterized.

A total-colored path is total rainbow if both its edges and internal vertices have distinct colors. The total rainbow connection number of a connected graph G, denoted by trc(G), is the smallest number of colors that are needed in a total-coloring of G in order to make G total rainbow connected, that is, any two vertices of G are connected by a total rainbow path. In this paper, we study the computational complexity of total rainbow connection of graphs. We show that deciding whether a given total-coloring...