Search

A defining set of a t-(υ, k, λ) design is a partial design which is contained in a unique t-design with the given parameters. A minimal defining set is a defining set, none of whose proper partial designs is a defining set. This paper proposes a new and more efficient algorithm that finds all nonisomorphic minimal defining sets of a given t-design. The complete list of minimal defining sets of 2-(6, 3, 6) designs, 2-(7, 3, 4) designs, the full 2-(7, 3, 5) design, a 2-(10, 4, 4) design, 2-(10, 5, 4) designs, 2-(13, 3, 1) designs, 2-(15, 3, 1) designs, the 2-(25, 5, 1) design, 3-(8, 4, 2) designs, the 3-(12, 6, 2) design, and 3-(16, 8, 3) designs are given to illustrate the efficiency of the algorithm. Also, corrections to the literature are made for the minimal defining sets of four 2-(7, 3, 3) designs, two 2-(6, 3, 4) designs and the 2-(21, 5, 1) design. Moreover, an infinite class of minimal defining sets for 2-(υ3) designs, where υ ≥ 5, has been constructed which helped to show that the difference between the sizes of the largest and the smallest minimal defining sets of 2-(υ3) designs gets arbitrarily large as υ→∞. Some results in the literature for the smallest defining sets of t-designs have been generalized to all minimal defining sets of these designs.We have also shown that all minimal defining sets of t-(2n, n, λ) designs can be constructed from the minimal defining sets of their restrictions when t is odd and all t-(2n, n, λ) [ABSTRACT FROM AUTHOR]

Let H be a set of undirected graphs. The induced H-packing problem in an input graph G is to find a subgraph Q of G of maximum size such that each connected component of Q is an induced subgraph of G and is isomorphic to some member of H. In this paper we focus on the case when H consists of factor-critical graphs and a certain family of 'propellers'. Clarifying the methods developed in the related theory of non-induced graph packings, we show a Gallai-Edmonds type structure theorem and a Berge-Tutte type minimax formula. We also give an Edmonds type alternating forest algorithm for the case when H consists of a sequential set of stars and factor-critical graphs. This simplifies the related result of Egawa, Kano and Kelmans. [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 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]

If m is a positive integer then we call a tree on at least 2 vertices an m- tree if no vertex is adjacent to more than m leaves. Kaneko proved that a connected, undirected graph G = ( V, E) has a spanning m-tree if and only if for every $$X \subseteq V$$ the number of isolated vertices of G − X is at most $$m|X|+{\rm max}\{0,|X| - 1\}$$ —unless we have the exceptional case of $$G \simeq K_3$$ and m = 1. As an attempt to integrate this result into the theory of graph packings, in this paper we consider the problem of packing a graph with m-trees. We use an approach different from that of Kaneko, and we deduce Gallai–Edmonds and Berge–Tutte type theorems and a matroidal result for the m-tree packing problem. [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]