Search

Let G be a graph and S ⊂ V( G). We denote by α( S) the maximum number of pairwise nonadjacent vertices in S. For x, y ∈ V( G), the local connectivity κ( x, y) is defined to be the maximum number of internally-disjoint paths connecting x and y in G. We define $$\kappa(S)=\min\{\kappa(x,y) : x,y \in S,x\not=y\}$$ . In this paper, we show that if κ( S) ≥ 3 and $$\sum_{i=1}^4 d_{G}{(x_i)} \ge |V(G)|+\kappa(S)+\alpha (S)-1$$ for every independent set { x 1, x 2, x 3, x 4} ⊂ S, then G contains a cycle passing through S. This degree condition is sharp and this gives a new degree sum condition for a 3-connected graph to be hamiltonian. [ABSTRACT FROM AUTHOR]

For an arbitrary class of graphs $$\mathcal{G}$$ , there may not exist a function f such that $$\chi(G) \leq f(\omega(G))$$ , for every $$G \in \mathcal{G}$$ . When such a function exists, it is called a χ-binding function for $$\mathcal{G}$$ . The problem of finding an optimal χ-binding function for the class of 3 K 1-free graphs is open. In this paper, we obtain linear χ-binding function for the class of {3 K 1, H}-free graphs, where H is one of the following graphs: $$K_1 + C_4, (K_3 \cup K_1)+K_1, K_1 + P_4, K_4 \cup K_1$$ , House graph and Kite graph. We first describe structures of these graphs and then derive χ-binding functions. [ABSTRACT FROM AUTHOR]

Let G be a connected graph. For $$x, y \in V(G)$$ at distance 2, we define $$J(x, y) = \{u|u \in N(x) \cap N(y), N[u] \subseteq N[x] \cup N[y]\}$$ , and $$J^{\prime}(x, y) = \{u|u \in N (x) \cap N(y)$$ , if $$v \in N(u) \setminus (N [x] \cup N[y])$$ then $$(N(u) \cup N(x) \cup N(y)) \setminus \{x,y,v\} \subseteq N(v)\}$$ . G is quasi-claw-free $$({\mathcal{QCF}})$$ if it satisfies $$J(x, y) \neq \emptyset$$ , and G is P 3-dominated( $$\mathcal{P}_{3}{\mathcal{D}}$$ ) if it satisfies $$J(x,y)\cup J^{\prime} (x,y) \neq \emptyset$$ , for every pair ( x, y) of vertices at distance 2. Certainly $${\mathcal{P}}_3 {\mathcal{D}}$$ contains $${\mathcal{QCF}}$$ as a subclass. In this paper, we prove that the circumference of a 2-connected P 3-dominated graph G on n vertices is at least min $$\{3\delta+2,n\}$$ or $$G \in {\mathcal{F}} \cup \{K_{2,3}, K_{1,1,3}\}$$ , moreover if $$n \leq 4\delta$$ then G is hamiltonian or $$G \in {\mathcal{F}}\cup\{K_{2,3}, K_{1,1,3}\}$$ , where $${\mathcal{F}}$$ is a class of 2-connected nonhamiltonian graphs. [ABSTRACT FROM AUTHOR]

Let γ pr ( G) denote the paired domination number of graph G. A graph G with no isolated vertex is paired domination vertex critical if for any vertex v of G that is not adjacent to a vertex of degree one, γ pr ( G – v) < γ pr ( G). We call these graphs γ pr -critical. In this paper, we present a method of constructing γ pr -critical graphs from smaller ones. Moreover, we show that the diameter of a γ pr -critical graph is at most $$\frac{3}{2}(\gamma_{pr} (G)-2)$$ and the upper bound is sharp, which answers a question proposed by Henning and Mynhardt [The diameter of paired-domination vertex critical graphs, Czechoslovak Math. J., to appear]. [ABSTRACT FROM AUTHOR]