Search

Let G be a graph and k an integer with 2 ≤ k ≤ n . The k-tree-connectivity of G, denoted by κ k (G) , is defined as the minimum κ G (S) over all k-subsets S of vertices, where κ G (S) denotes the maximum number of internally disjoint S-trees in G. The k-path-connectivity of G, denoted by π k (G) , is defined as the minimum π G (S) over all k-subsets S of vertices, where π G (S) denotes the maximum number of internally disjoint S-paths in G. In this paper, we first prove that for any fixed integer k ≥ 1 , given a graph G and a subset S of V(G), deciding whether π G (S) ≥ k is NP -complete. Moreover, we also show that for any fixed integer k 1 ≥ 5 , given a graph G, a k 1 -subset S of V(G) and an integer 1 ≤ k 2 ≤ n - 1 , deciding whether π G (S) ≥ k 2 is NP -complete. Let π (k , ℓ) = 1 + max { κ (G) | G \ is\ a\ graph\ with π k (G) < ℓ } . Hager (Discrete Math 59:53–59, 1986) showed that ℓ (k - 1) ≤ π (k , ℓ) ≤ 2 k - 2 ℓ and conjectured that π (k , ℓ) = ℓ (k - 1) for k ≥ 2 and ℓ ≥ 1 . He also confirmed the conjecture for 2 ≤ k ≤ 4 and proved π (5 , ℓ) ≤ ⌈ 9 2 ℓ ⌉ . By introducing a "Generalized Path-Bundle Transformation", we confirm the conjecture for k = 5 and prove that π (k , ℓ) ≤ 2 k - 3 ℓ for k ≥ 5 and ℓ ≥ 1 . By employing this transformation, we also prove that if G is a graph with κ (G) ≥ (k - 1) ℓ for any k ≥ 2 and ℓ ≥ 1 , then κ k (G) ≥ ℓ . [ABSTRACT FROM AUTHOR]

A set S of vertices in a graph G is an independent dominating set of G if S is an independent set and every vertex not in S is adjacent to a vertex in S. The independent domination number of G, denoted by i(G), is the minimum cardinality of an independent dominating set. In this paper, we study the following conjecture posed by Goddard and Henning (Discrete Math. 313:839–854, 2013): If G ≇ K 3 , 3 is a connected, cubic, bipartite graph on n vertices, then i (G) ≤ 4 11 n . Henning et al. (Discrete Appl. Math. 162:399–403, 2014) prove the conjecture when the girth is at least 6. In this paper we strengthen this result by proving the conjecture when the graph has no subgraph isomorphic to K 2 , 3 . [ABSTRACT FROM AUTHOR]

Let k be a positive integer and let D be a digraph. A path partition P of D is a set of vertex-disjoint paths which covers V(D). Its k-norm is defined as ∑ P ∈ P min { | V (P) | , k } . A path partition is k-optimal if its k-norm is minimum among all path partitions of D. A partialk-coloring is a collection of k disjoint stable sets. A partial k-coloring C is orthogonal to a path partition P if each path P ∈ P meets min { | V (P) | , k } distinct sets of C . Berge (Eur J Comb 3(2):97–101, 1982) conjectured that every k-optimal path partition of D has a partial k-coloring orthogonal to it. A (path) k-pack of D is a collection of at most k vertex-disjoint paths in D. Its weight is the number of vertices it covers. A k-pack is optimal if its weight is maximum among all k-packs of D. A coloring of D is a partition of V(D) into stable sets. A k-pack P is orthogonal to a coloring C if each set C ∈ C meets min { | C | , k } paths of P . Aharoni et al. (Pac J Math 2(118):249–259, 1985) conjectured that every optimal k-pack of D has a coloring orthogonal to it. A digraph D is semicomplete if every pair of distinct vertices of D are adjacent. A digraph D is locally in-semicomplete if, for every vertex v ∈ V (D) , the in-neighborhood of v induces a semicomplete digraph. Locally out-semicomplete digraphs are defined similarly. In this paper, we prove Berge's and Aharoni–Hartman–Hoffman's Conjectures for locally in/out-semicomplete digraphs. [ABSTRACT FROM AUTHOR]

A proper edge k-colouring of a graph $$G=(V,E)$$ is an assignment $$c:E\rightarrow \{1,2,\ldots ,k\}$$ of colours to the edges of the graph such that no two adjacent edges are associated with the same colour. A neighbour sum distinguishing edge k-colouring, or nsd k-colouring for short, is a proper edge k-colouring such that $$\sum _{e\ni u}c(e)\ne \sum _{e\ni v}c(e)$$ for every edge uv of G. We denote by $$\chi '_{\Sigma }(G)$$ the neighbour sum distinguishing index of G, which is the least integer k such that an nsd k-colouring of G exists. By definition at least maximum degree, $$\Delta (G)$$ colours are needed for this goal. In this paper we prove that $$\chi '_\Sigma (G) \le \Delta (G)+1$$ for any graph G without isolated edges, with $$\mathrm{mad}(G)<3$$ and $$\Delta (G) \ge 6$$ . [ABSTRACT FROM AUTHOR]