Search

Brown et al. (J Combin Theory Ser B 15(1):77–93, 1973) considered Turán-type extremal problems for digraphs. However, to date there are very few results on this problem, even asymptotically. Let P 2 , 2 → be the orientation of C 4 which consists of two 2-paths with the same initial and terminal vertices. Huang and Lyu [Discrete Math., 343 (5) (2020)] recently determined the Turán number of P 2 , 2 → , and considered it a more natural and interesting problem to determine the Turán number of directed cycles. Let P k → and C k → denote the directed path and the directed cycle of order k, respectively. In this paper we determine the maximum size of C k → -free digraphs of order n for all n , k ∈ N ∗ , as well as the extremal digraphs attaining this maximum size. Similar result is obtained for P k → where n is large. In addition, we generalize the result of Huang and Lyu by characterizing the extremal digraphs avoiding an arbitrary orientation of C 4 except P 2 , 2 → . In particular, for oriented even cycles, we classify which oriented even cycles inherit the difficulty of their underlying graphs and which do not. [ABSTRACT FROM AUTHOR]

Henning et al. (Discrete Appl Math 162:399–403, 2014) proved that if G is a bipartite, cubic graph of order n and of girth at least 6, then i (G) ≤ 4 11 n . In this paper, we improve the 4 11 -bound to a 5 14 -bound, and prove that if G is a bipartite, cubic graph of order n and of girth at least 6, then i (G) ≤ 5 14 n . [ABSTRACT FROM AUTHOR]

Graphs considered in this paper are finite, undirected and without loops, but with multiple edges. For an integer t ≥ 1 , denote by MG t the class of graphs whose maximum multiplicity is at most t. A graph G is called strictly t-degenerate if every non-empty subgraph H of G contains a vertex v whose degree in H is at most t - 1 . The point partition number χ t (G) of G is the smallest number of colors needed to color the vertices of G so that each vertex receives a color and vertices with the same color induce a strictly t-degenerate subgraph of G. So χ 1 is the chromatic number, and χ 2 is known as the point aboricity. The point partition number χ t with t ≥ 1 was introduced by Lick and White (Can J Math 22:1082–1096, 1970). If H is a simple graph, then tH denotes the graph obtained from H by replacing each edge of H by t parallel edges. Then ω t (G) is the largest integer n such that G contains a t K n as a subgraph. Let G be a graph belonging to MG t . Then ω t (G) ≤ χ t (G) and we say that G is χ t -perfect if every induced subgraph H of G satisfies ω t (H) = χ t (H) . Based on the Strong Perfect Graph Theorem due to Chudnowsky, Robertson, Seymour and Thomas (Ann Math 164:51–229, 2006), we give a characterization of χ t -perfect graphs of MG t by a set of forbidden induced subgraphs (see Theorems 2 and 3). We also discuss some complexity problems for the class of χ t -critical graphs. [ABSTRACT FROM AUTHOR]

A dominating set of a graph G is a set S ⊆ V such that every vertex in G is either in S or is adjacent to a vertex in S. A dominating set S is an outer connected dominating set if the induced subgraph G [ V \ S ] is connected. The domination number (outer connected domination number, respectively) of G, denoted by γ (G) ( γ c ~ (G) , respectively), is the minimum cardinality of a dominating set (outer connected dominating set, respectively). In this paper, we show that the outer connected domination number of a maximal outerplanar graph G is bounded by min { ⌊ n + k 4 ⌋ , ⌊ n 3 ⌋ } , where k is the number of vertices of degree 2 in G. On the other hand, in Campos and Wakabayashi (Discrete Appl Math 161:330–335, 2013), Campos and Wakabayashi show that if G is a striped maximal outerplanar graph of order n ≥ 3 , then γ (G) ≤ ⌊ n 4 ⌋ when n ≡ 0 , 1 ( mod 4), and γ (G) ≤ ⌈ n 4 ⌉ otherwise. We characterize all graphs achieving equality for this bound. Moreover, we slightly improve this bound. [ABSTRACT FROM AUTHOR]

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]

For a graph G, define σ 2 (G) by σ 2 (G) = min { d G (x) + d G (y) : x , y ∈ V (G) , x ≠ y , x y ∉ E (G) } . If G is a bipartite graph with partite sets X and Y, we also define σ 1 , 1 (G) by σ 1 , 1 (G) = min { d G (x) + d G (y) : x ∈ X , y ∈ Y , x y ∉ E (G) } . Ore's theorem states that a graph of order n ≥ 3 with σ 2 (G) ≥ n contains a hamiltonian cycle and the Moon–Moser theorem states that a balanced bipartite graph G of order 2 n ≥ 4 with σ 1 , 1 (G) ≥ n + 1 contains a hamiltonian cycle. In Chen et al. (Discrete Math 343:Article No. 111663, 2020), we studied the relationship between Ore's theorem and the Moon–Moser theorem, and proved that the refinement of the Moon–Moser theorem given by Ferrara et al. (Discrete Math 312:459–461, 2012) implies Ore's theorem for graphs of even order. In this paper, we extend the above study to the graphs of odd order. Since no graphs of odd order contain a spanning balanced bipartite subgraph, the Moon–Moser theorem does not work in this case. We instead introduce its counterpart for the graphs in which the orders of the partite sets differ by 1, proved in Matsubara et al. (Discrete Math 340:87–95, 2017). We refine this result and prove that this refinement implies Ore's theorem. [ABSTRACT FROM AUTHOR]

A subset T of vertices in a hypergraph H is a transversal if T has a nonempty intersection with every edge of H. The transversal number τ (H) of H is the minimum size of a transversal in H. A hypergraph H is 3-uniform if every edge of H has size 3. Let H be a 3-uniform hypergraph with n H vertices and m H edges. Tuza (Discrete Math 86:117–126, 1990) and Chvátal and McDiarmid (Combinatorica 12:19–26, 1992) showed that 4 τ (H) ≤ n H + m H . Chvátal and McDiarmid also showed that 6 τ (H) ≤ 2 n H + m H . The linear hypergraphs achieving equality in these bounds were characterized by the authors (Henning and Yeo in J Graph Theory 59:326–348, 2008; Discrete Math 313:959–966, 2013). In this paper, we show that these bounds can be improved if we impose some structural properties on H. We show that if H does not contain a subhypergraph isomorphic to the affine plane AG(2, 3) of order 3 with two vertices deleted, then 17 τ (H) ≤ 5 n H + 3 m H . The total domination number γ t (G) of a graph G is the minimum cardinality of a set S of vertices so that every vertex in G is adjacent to some vertex in S. It is known (Archdeacon et al. in J Graph Theory 46:207–210, 2004) that if G is a graph of order n with minimum degree at least 3, then γ t (G) ≤ 1 2 n , and that this bound is tight. As a consequence of our hypergraph results, we show that if G is a graph of order n with minimum degree at least 3 that contains no 4-cycles and no specified graph on 12 vertices as a subgraph, then γ t (G) ≤ 8 17 n . [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]

A subset N of V(D) is said to be a kernel if it satisfies the following two properties: (1) for any two different vertices x and y in N there is no arc between them, and (2) for each vertex u in V(D) \ N there exists v in N such that (u,v) ∈ A(D). If every induced subdigraph of D has a kernel, D is said to be a kernel perfect digraph. In Galeana-Sánchez and Rojas-Monroy (Discrete Math, 275: 129–136, 2004) and Galeana-Sánchez and Rojas-Monroy (Discrete Math. 306: 1969–1974, 2006) the authors establish sufficient conditions to guarantee the kernel perfectness in digraphs, possibly infinite, where their set of arcs can be partitioned into at most two pre-transitive (resp. quasi-transitive) digraphs. In the present paper we consider those, also possibly infinite, digraphs where the set of arcs can be partitioned into at least three quasi-transitive (resp. pre-transitive) digraphs, and establish sufficient conditions to guarantee the kernel perfectness. In both cases we derive Richardson's theorem, which states that every finite digraph without cycles of odd length has a kernel. [ABSTRACT FROM AUTHOR]

Let H be a connected hypergraph with minimum degree δ and edge-connectivity λ . The hypergraph H is maximally edge-connected if λ = δ , and it is super edge-connected or super- λ , if every minimum edge-cut consists of edges incident with some vertex. There are several degree sequence conditions, for example, Goldsmith and White (Discrete Math 23: 31–36, 1978) and Bollobás (Discrete Math 28:321–323, 1979) etc. for maximally edge-connected graphs and super- λ graphs. In this paper, we generalize these and some other degree sequence conditions to uniform hypergraphs. [ABSTRACT FROM AUTHOR]

In this paper, we show the following: Let G be a connected claw-free graph such that G has a connected induced subgraph H that has a pair of vertices { v 1 , v 2 } of degree one in H whose distance is d + 2 in H. Then H has an induced subgraph F, which is isomorphic to B i , j , with { v 1 , v 2 } ⊆ V (F) and i + j = d + 1 , with a well-defined exception. Here B i , j denotes the graph obtained by attaching two vertex-disjoint paths of lengths i , j ≥ 1 to a triangle. We also use the result above to strengthen the results in Xiong et al. (Discrete Math 313:784–795, 2013) in two cases, when i + j ≤ 9 , and when the graph is Γ 0 -free. Here Γ 0 is the simple graph with degree sequence 4, 2, 2, 2, 2. Let i , j > 0 be integers such that i + j ≤ 9 . Then every 3-connected { K 1 , 3 , B i , j } -free graph G is hamiltonian, and every 3-connected { K 1 , 3 , Γ 0 , B 2 i , 2 j } -free graph G is hamiltonian. The two results above are all sharp in the sense that the condition " i + j ≤ 9 " couldn't be replaced by ' ' i + j ≤ 10 ". [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 graph is called a weighted graph when each edge e is assigned a nonnegative number w( e), called the weight of e. For a vertex v of a weighted graph, d w( v) is the sum of the weights of the edges incident with v. For a subgraph H of a weighted graph G, the weight of H is the sum of the weights of the edges belonging to H. In this paper, we give a new sufficient condition for a weighted graph to have a heavy cycle. A 2-connected weighted graph G contains either a Hamilton cycle or a cycle of weight at least c, if G satisfies the following conditions: In every induced claw or induced modified claw F of G, (1) max{ d w( x), d w( y)}≥ c/2 for each non-adjacent pair of vertices x and y in F, and (2) all edges of F have the same weight. [ABSTRACT FROM AUTHOR]

The notion of travel groupoids was introduced by Nebeský in 2006 in connection with a study on geodetic graphs. A travel groupoid is a pair of a set V and a binary operation $$*$$ on V satisfying two axioms. For a travel groupoid, we can associate a graph. We say that a graph G has a travel groupoid if the graph associated with the travel groupoid is equal to G. Nebeský gave a characterization for finite graphs to have a travel groupoid. In this paper, we introduce the notion of T-neighbor systems on a graph and give a characterization of travel groupoids on a graph in terms of T-neighbor systems. [ABSTRACT FROM AUTHOR]

In this paper, we investigate suborbital graph for the normalizer of $$\varGamma _0(N)$$ in $$PSL(2,\mathbb {R})$$ , where N will be of the form $$2^23p^2$$ , p is prime number greater than 3 and $$p\equiv 1\pmod {3}$$ . Then we give edge and circuit conditions on graphs arising from the imprimitive action of the normalizer. [ABSTRACT FROM AUTHOR]

If $$\mu _m$$ and $$d_m$$ denote, respectively, the m-th largest Laplacian eigenvalue and the m-th largest vertex degree of a graph, then $$\mu _m \geqslant d_m-m+2$$ . This inequality was conjectured by Guo (Linear Multilinear Algebra 55:93-102, 2007) and proved by Brouwer and Haemers (Linear Algebra Appl 429:2131-2135, 2008). Brouwer and Haemers gave several examples of graphs achieving equality, but a complete characterisation was not given. In this paper we consider the problem of characterising graphs satisfying $$\mu _m = d_m-m+2$$ . In particular we give a full classification of graphs with $$\mu _m = d_m-m+2 \leqslant 1$$ . [ABSTRACT FROM AUTHOR]

The coboundary expansion generalizes the classical graph expansion to the case of the general simplicial complexes, and allows the definition of the higher-dimensional Cheeger constants $$h_k(X)$$ for an arbitrary simplicial complex X, and any $$k\ge 0$$ . In this paper we investigate the value of $$h_1(\Delta ^{[n]})$$ -the first Cheeger constant of a simplex with n vertices. It is known, due to the pioneering work of Meshulam and Wallach [12], that and that the equality $$h_1(\Delta ^{[n]})=n/3$$ is achieved when n is divisible by 3. Here we expand on these results. First, we show that So the sharp equality holds on a set whose density goes to 1. Second, we show that In other words, as n goes to infinity, the value $$h_1(\Delta ^{[n]})-n/3$$ is either 0 or goes to 0 very rapidly. Our methods include recasting the original question in purely graph-theoretic language, followed by a detailed investigation of a specific graph family, the so-called staircase graphs. These are defined by associating a graph to every partition, and appear to be especially suited to gain information about the first Cheeger constant of a simplex. [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]

A graph is well-covered if all its maximal independent sets are of the same cardinality (Plummer in J Comb Theory 8:91-98, 1970). If G is a well-covered graph with at least two vertices, and $$G{-}v$$ is well-covered for every vertex v, then G is a 1- well-covered graph (Staples in On some subclasses of well-covered graphs. Ph.D. Thesis, Vanderbilt University, 1975). The graph G is $$\lambda $$ - quasi-regularizable if $$\lambda >0$$ and $$\lambda \cdot \vert S\vert \le \vert N( S) \vert $$ for every independent set S of G. It is known that every well-covered graph without isolated vertices is 1-quasi-regularizable (Berge in Ann Discret Math 12:31-44, 1982). The independence polynomial $$I(G;x)= {\sum _{k=0}^{\alpha }} s_{k}x^{k}$$ is the generating function of independent sets in a graph G (Gutman and Harary in Util Math 24:97-106, 1983), where $$\alpha $$ is the independence number of G. The Roller-Coaster Conjecture (Michael and Traves in Graphs Comb 19:403-411, 2003), saying that for every permutation $$\sigma $$ of the set $$\{\lceil \frac{\alpha }{2}\rceil ,\ldots ,\alpha \}$$ there exists a well-covered graph G with the independence number $$\alpha $$ such that the coefficients $$( s_{k}) $$ of I( G; x) satisfy has been validated in Cutler and Pebody (J Comb Theory A 145:25-35, 2017). In this paper we show that independence polynomials of $$\lambda $$ -quasi-regularizable graphs are partially unimodal. More precisely, the coefficients of an upper part of I( G; x) are in non-increasing order. Based on this finding, we prove that the unconstrained part of the independence sequence is: for well-covered graphs, and for 1-well-covered graphs, where $$\alpha $$ stands for the independence number, and n is the cardinality of the vertex set. [ABSTRACT FROM AUTHOR]

An edge-transitive graph $$\varGamma $$ is called alternatively connected if a subgroup G of the automorphism group of $$\varGamma $$ has two orbits on the arc set of $$\varGamma $$ , and there exists an alternative walk (with respect to a given G-orbit on arcs) between every pair of vertices of $$\varGamma $$ . Employing the standard double covers of digraphs, we give some basic properties of alternatively connected edge-transitive graphs. The main result of this paper is a reduction result on alternatively connected edge-transitive graphs of square-free order. As an application of this result, we give a characterization for alternatively connected edge-transitive graphs of square-free order and valency 6. It is proved that such a graph is either a circulant or constructed from $$\mathrm{PSL}(2,p)$$ . [ABSTRACT FROM AUTHOR]

A subset U of vertices of a graph G is called a determining set if every automorphism of G is uniquely determined by its action on the vertices of U. A subset W is called a resolving set if every vertex in G is uniquely determined by its distances to the vertices of W. Determining (resolving) sets are said to have the exchange property in G if whenever S and R are minimal determining (resolving) sets for G and $${r\in R}$$ , then there exists $${s\in S}$$ so that $${S-\{s\} \cup \{r\}}$$ is a minimal determining (resolving) set. This work examines graph families in which these sets do, or do not, have the exchange property. This paper shows that neither determining sets nor resolving sets have the exchange property in all graphs, but that both have the exchange property in trees. It also gives an infinite graph family ( n-wheels where n ≥ 8) in which determining sets have the exchange property but resolving sets do not. Further, this paper provides necessary and sufficient conditions for determining sets to have the exchange property in an outerplanar graph. [ABSTRACT FROM AUTHOR]

Consider anm×nzero-one matrixA. Ans×tsubmatrix ofAis said to beevenif the sum of its entries is even. In this paper, we focus on the casem=nands=t=2. ThemaximumnumberM(n) of even 2×2 submatrices ofAis clearlyand corresponds to the matrixAhaving, e.g., all ones (or zeros). A more interesting question, motivated by Turán numbers and Hadamard matrices, is that of theminimumnumberm(n) of such matrices. It has recently been shown thatfor some constantB. In this paper we show that if the matrixA=A n is considered to be induced by an infinite zero one matrix obtained at random, thenwhereE n denotes the number of even 2×2 submatrices ofA n. Results such as these provide us with specific information about the tightness of the concentration ofE n around its expected value of [ABSTRACT FROM AUTHOR]

Given a distribution of pebbles on the vertices of a connected graph G, a pebbling move is defined as the removal of two pebbles from some vertex and the placement of one of these on an adjacent vertex. The pebbling number of a graph G is the smallest integer k such that for each vertex v and each distribution of k pebbles on G there is a sequence of pebbling moves that places at least one pebble on v. We say such a distribution is solvable. The optimal pebbling number of G, denoted $$\varPi _{OPT}(G)$$ , is the least k such that some particular distribution of k pebbles is solvable. In this paper, we strengthen a result of Bunde et al. relating to the optimal pebbling number of the 2 by n square grid by describing all possible optimal configurations. We find the optimal pebbling number for the 3 by n grid and related structures. Finally, we give a bound for the analogue of this question for the infinite square grid. [ABSTRACT FROM AUTHOR]

Let $$G=(V,E)$$ be any graph without isolated vertices. For some $$\alpha $$ with $$0<\alpha \le 1$$ and a dominating set S of G, we say that S is an $$\alpha $$ -dominating set if for any $$v\in V-S, |N(v)\cap S| \ge \alpha |N(v)|$$ . The cardinality of a smallest $$\alpha $$ -dominating set of G is called the $$\alpha $$ -domination number of G and is denoted by $$\gamma _{\alpha }(G)$$ . In this paper, we study graphs G for which the removal of any edge or the addition of any further edge affects the $$\alpha $$ -domination number of G. [ABSTRACT FROM AUTHOR]

A total weighting of a graph G is a mapping $$\varphi $$ that assigns a weight to each vertex and each edge of G. The vertex-sum of $$v \in V(G)$$ with respect to $$\varphi $$ is $$S_{\varphi }(v)=\sum _{e\in E(v)}\varphi (e)+\varphi (v)$$ . A total weighting is proper if adjacent vertices have distinct vertex-sums. A graph $$G=(V,E)$$ is called $$(k,k{^{\prime }})$$ -choosable if the following is true: For any total list assignment L which assigns to each vertex v a set L( v) of k real numbers, and assigns to each edge e a set L( e) of $$k{^{\prime }}$$ real numbers, there is a proper total weighting $$\varphi $$ with $$\varphi (y)\in L(y)$$ for any $$y \in V \cup E$$ . In this paper, we prove that for any graph $$G\ne K_1$$ , for any positive integer m, the m-cone graph of G is (1, 4)-choosable. Moreover, we give some sufficient conditions for the m-cone graph of G to be (1, 3)-choosable. In particular, if G is a tree, a complete bipartite graph or a generalized $$\theta $$ -graph, then the m-cone graph of G is (1, 3)-choosable. [ABSTRACT FROM AUTHOR]

A graph G is called claw-o-heavy if every induced claw ( $$K_{1,3}$$ ) of G has two end-vertices with degree sum at least | V( G)|. For a given graph S, G is called S-f-heavy if for every induced subgraph H of G isomorphic to S and every pair of vertices $$u,v\in V(H)$$ with $$d_H(u,v)=2,$$ there holds $$\max \{d(u),d(v)\}\ge |V(G)|/2.$$ In this paper, we prove that every 2-connected claw- o-heavy and $$Z_3$$ - f-heavy graph is hamiltonian (with two exceptional graphs), where $$Z_3$$ is the graph obtained by identifying one end-vertex of $$P_4$$ (a path with 4 vertices) with one vertex of a triangle. This result gives a positive answer to a problem proposed Ning and Zhang (Discrete Math 313:1715-1725, ), and also implies two previous theorems of Faudree et al. and Chen et al., respectively. [ABSTRACT FROM AUTHOR]

A pure Mendelsohn triple system of order v, denoted by PMTS( v), is a pair $$(X,\mathcal {B})$$ where X is a v-set and $$\mathcal {B}$$ is a collection of cyclic triples on X such that every ordered pair of X belongs to exactly one triple of $$\mathcal {B}$$ and if $$\langle a,b,c\rangle \in \mathcal {B}$$ implies $$\langle c,b,a\rangle \notin \mathcal {B}$$ . An overlarge set of PMTS( v), denoted by OLPMTS( v), is a collection $$\{(Y{\setminus }\{y_i\},{\mathcal {A}}_i)\}_i$$ , where Y is a $$(v+1)$$ -set, $$y_i\in Y$$ , each $$(Y{\setminus }\{y_i\},{\mathcal {A}}_i)$$ is a PMTS( v) and these $${\mathcal {A}}_i$$ s form a partition of all cyclic triples on Y. It is shown in [] that there exists an OLPMTS( v) for $$v\equiv 1,3$$ (mod 6), $$v>3$$ , or $$v \equiv 0,4$$ (mod 12). In this paper, we shall discuss the existence problem of OLPMTS( v) s for $$v\equiv 6,10$$ (mod 12) and get the following conclusion: there exists an OLPMTS( v) if and only if $$v\equiv 0,1$$ (mod 3), $$v>3$$ and $$v\ne 6$$ . [ABSTRACT FROM AUTHOR]

A proper edge-coloring of a graph defines at each vertex the set of colors of its incident edges. This set is called the palette of the vertex. In this paper we are interested in the minimum number of palettes taken over all possible proper colorings of a graph. [ABSTRACT FROM AUTHOR]

An edge cut of a connected graph is 5-restricted if its removal leaves every component having order at least five. Graphs that contain 5-restricted edge cuts are characterized in this paper. As a result, it is shown that a connected graph G of order at least 13 contains 5-restricted edge cuts if and only if $${G \setminus v}$$ contains a component of order at least five for every vertex v of graph G. [ABSTRACT FROM AUTHOR]

Let $${\mathcal{F}}$$ be a family of connected graphs. A graph G is said to be $${\mathcal{F}}$$-free if G is H-free for every graph H in $${\mathcal{F}}$$. We study the problem of characterizing the families of graphs $${\mathcal{F}}$$ such that every large enough connected $${\mathcal{F}}$$-free graph of even order has a perfect matching. This problems was previously studied in Plummer and Saito (J Graph Theory 50(1):1-12, ), Fujita et al. (J Combin Theory Ser B 96(3):315-324, ) and Ota et al. (J Graph Theory, 67(3):250-259, ), where the authors were able to characterize such graph families $${\mathcal{F}}$$ restricted to the cases $${|\mathcal{F}|\leq 1, |\mathcal{F}| \leq 2}$$ and $${|\mathcal{F}| \leq 3}$$, respectively. In this paper, we complete the characterization of all the families that satisfy the above mentioned property. Additionally, we show the families that one gets when adding the condition $${|\mathcal{F}| \leq k}$$ for some k ≥ 4. [ABSTRACT FROM AUTHOR]

The problem of determining the chromatic number of H-free graphs has been well studied, with particular attention to K-free graphs with large minimum degree. Recent progress has been made for triangle-free graphs on n vertices with minimum degree larger than n/3. In this paper, we determine the family of r-colorable graphs $${\mathcal{H}_r}$$, such that if $${H \in \mathcal{H}_r}$$, there exists a constant C < ( r − 2)/( r − 1) such that any H-free graph G on n vertices with δ( G) > Cn has chromatic number bounded above by a function dependent only on H and C. A value of C < ( r − 2)/( r − 1) is given for every $${H \in \mathcal{H}_r}$$, with particular attention to the case when χ( H) = 3. [ABSTRACT FROM AUTHOR]

A graph is total domination edge-critical if the addition of any edge decreases the total domination number, while a graph with minimum degree at least two is total domination vertex-critical if the removal of any vertex decreases the total domination number. A 3 EC graph is a total domination edge-critical graph with total domination number 3 and a 3 VC graph is a total domination vertex-critical graph with total domination number 3. A graph G is factor-critical if G − v has a perfect matching for every vertex v in G. In this paper, we show that every 3 EC graph of even order has a perfect matching, while every 3 EC graph of odd order with no cut-vertex is factor-critical. We also show that every 3 VC graph of even order that is K-free has a perfect matching, while every 3 VC graph of odd order that is K-free is factor-critical. We show that these results are tight in the sense that there exist 3 VC graphs of even order with no perfect matching that are K-free and 3 VC graphs of odd order that are K-free but not factor-critical. [ABSTRACT FROM AUTHOR]

In this paper, we present new upper bounds for the global domination and Roman domination numbers and also prove that these results are asymptotically best possible. Moreover, we give upper bounds for the restrained domination and total restrained domination numbers for large classes of graphs, and show that, for almost all graphs, the restrained domination number is equal to the domination number, and the total restrained domination number is equal to the total domination number. A number of open problems are posed. [ABSTRACT FROM AUTHOR]

In 1966, Barnette introduced a set of graphs, called circuit graphs, which are obtained from 3-connected planar graphs by deleting a vertex. Circuit graphs and 3-connected planar graphs share many interesting properties which are not satisfied by general 2-connected planar graphs. Circuit graphs have nice closure properties which make them easier to deal with than 3-connected planar graphs for studying some graph-theoretic properties. In this paper, we study some enumerative properties of circuit graphs. For enumeration purpose, we define rooted circuit maps and compare the number of rooted circuit maps with those of rooted 2-connected planar maps and rooted 3-connected planar maps. [ABSTRACT FROM AUTHOR]

A star-factor of a graph is a spanning subgraph each of whose components is a star. A graph G is called star-uniform if all star-factors of G have the same number of components. Motivated by the minimum cost spanning tree and the optimal assignment problems, Hartnell and Rall posed an open problem to characterize all the star-uniform graphs. In this paper, we show that a graph G is star-uniform if and only if G has equal domination and matching number. From this point of view, the star-uniform graphs were characterized by Randerath and Volkmann. Unfortunately, their characterization is incomplete. By deploying Gallai–Edmonds Matching Structure Theorem, we give a clear and complete characterization of star-unform graphs. [ABSTRACT FROM AUTHOR]

A k-tree is a tree with maximum degree at most k. In this paper, we give sufficient conditions for a graph to have a k-tree containing specified vertices. Let k be an integer with k ≥ 3. Let G be a graph of order n and let S ⊆ V(G) with ?(S) ≥ 1. Suppose that for every l ≥ :(S), there exists an integer t such that 1 ≤ t ≤ (k - 1)l + 2 - [l-1/k ] and the degree sum of any t independent vertices of S is at least n +tl -kl -1. Then G has a k-tree containing S.We also show some new results on a spanning k-tree as corollaries of the above theorem. [ABSTRACT FROM AUTHOR]

Let Γ be a Delsarte set graph with an intersection number c2 (i.e., a distance-regular graph with a set C of Delsarte cliques such that each edge lies in a positive constant number nC of Delsarte cliques in C). We showed in Bang et al. (J Combin 28:501-506, 2007) that if ψ1 > 1 then c2 ≥ 2ψ1 where ψ1 := ΙΓ1 (x)∩CΙ for x ∈ V(Γ) and C a Delsarte clique satisfying d(x,C) = 1. In this paper,we classify Γ with the case c2 = 2ψ1 > 2. As a consequence of this result, we show that if c2 ≤ 5 and ψ1 > 1 then Γ is either a Johnson graph or a folded Johnson graph J (4s, 2s) with s ≥ 3. [ABSTRACT FROM AUTHOR]

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]

A directed graph has a natural Z-module homomorphism from the underlying graph's cycle space to Z where the image of an oriented cycle is the number of forward edges minus the number of backward edges. Such a homomorphism preserves the parity of the length of a cycle and the image of a cycle is bounded by the length of that cycle. Pretzel and Youngs (SIAM J. Discrete Math. 3(4):544-553, 1990) showed that any Z-module homomorphism of a graph's cycle space to Z that satisfies these two properties for all cycles must be such a map induced from an edge direction on the graph. In this paper we will prove a generalization of this theorem and an analogue as well. [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]

Let H be a multigraph, possibly containing loops. An H-subdivision is any simple graph obtained by replacing the edges of H with paths of arbitrary length. Let H be an arbitrarymultigraph of order k, sizem, n0(H) isolated vertices and n1(H) vertices of degree one. In Gould and Whalen (Graphs Comb. 23:165-182, 2007) it was shown that if G is a simple graph of order n containing an H-subdivision H and δ(G) ≥ n+m-k+n1(H)+2n0(H)/2 , then G contains a spanning H-subdivision with the same ground set as H. As a corollary to this result, the authors were able to obtain Dirac's famed theorem on hamiltonian graphs; namely that if G is a graph of order n ≥ 3with δ(G) ≥ n/2 , then G is hamiltonian. Bondy (J.Comb.Theory Ser.B11:80-84, 1971) extended Dirac's theorem by showing that if G satisfied the condition δ(G) ≥ n/2 then G was either pancyclic or a complete bipartite graph. In this paper, we extend the result from Gould and Whalen (Graphs Comb. 23:165-182, 2007) in a similar manner. An H-subdivisionHin G is 1-extendible if there exists an H-subdivision H* with the same ground set as H and ∣H*∣ = ∣H∣ + 1. If every H-subdivision in G is 1-extendible, then G is pan-H-linked. We demonstrate that if H is sufficiently dense and G is a graph of large enough order n such that δ(G) ≥ n+m-k+n1(H)+2n0(H)/2 , then G is pan-H-linked. This result is sharp. [ABSTRACT FROM AUTHOR]

A graph of order n is said to be pancyclic if it contains cycles of all lengths from three to n. Let G be a Hamiltonian graph and let x and y be vertices of G that are consecutive on some Hamiltonian cycle in G. Hakimi and Schmeichel showed (J Combin Theory Ser B 45:99-107, 1988) that if d(x) + d(y) ≥ n then either G is pancyclic, G has cycles of all lengths except n - 1 or G is isomorphic to a complete bipartite graph. In this paper, we study the existence of cycles of various lengths in a Hamiltonian graph G given the existence of a pair of vertices that have a high degree sum but are not adjacent on any Hamiltonian cycle in G. [ABSTRACT FROM AUTHOR]

Let r and s be nonnegative integers, and let G be a graph of order at least 3r + 4s. In Bialostocki et al. (Discrete Math 308:5886-5890, 2008), conjectured that if the minimum degree of G is at least 2r + 3s, then G contains a collection of r + s vertex-disjoint cycles such that s of them are chorded cycles, and they showed that the conjecture is true for r = 0, s = 2 and for s = 1. In this paper, we settle this conjecture completely by proving the following stronger statement; if the minimum degree sum of two nonadjacent vertices is at least 4r + 6s - 1, then G contains a collection of r + s vertex-disjoint cycles such that s of them are chorded cycles. [ABSTRACT FROM AUTHOR]

Let G be a simple 3-connected graph. An edge e of G is essential if neither the deletion G\ e nor the contraction G/ e is both simple and 3-connected. In this study, we show that all 3-connected graphs with k( k ≥ 2) non-essential edges can be obtained from a wheel by three kinds of operations which defined in the paper. [ABSTRACT FROM AUTHOR]

A Steiner triple system of order ν, denoted STS( ν), is said to be tricyclic if it admits an automorphism whose disjoint cyclic decomposition consists of three cycles. In this paper we give necessary and sufficient conditions for the existence of a tricyclic STS( ν) for several cases. We also pose conjectures concerning their existence in two remaining cases. [ABSTRACT FROM AUTHOR]

Inspired by connections described in a recent paper by Mark L. Lewis, between the common divisor graph Γ( X) and the prime vertex graph Δ( X), for a set X of positive integers, we define the bipartite divisor graph B( X), and show that many of these connections flow naturally from properties of B( X). In particular we establish links between parameters of these three graphs, such as number and diameter of components, and we characterise bipartite graphs that can arise as B( X) for some X. Also we obtain necessary and sufficient conditions, in terms of subconfigurations of B( X), for one of Γ( X) or Δ( X) to contain a complete subgraph of size 3 or 4. [ABSTRACT FROM AUTHOR]

Necessary conditions for a simple connected graph G to admit a decomposition into closed trails of length k ≥ 3 are that G is even and its total number of edges is a multiple of k. In this paper we show that these conditions are sufficient in the case when G is the complete equipartite graph having at least three parts, each of the same size. [ABSTRACT FROM AUTHOR]

A defining set of a t-( v, k, λ) design is a subcollection of its blocks which is contained in no other t-design with the given parameters, on the same point set. A minimal defining set is a defining set, none of whose proper subcollections is a defining set. The spectrum of minimal defining sets of a design D is the set {| M| | M is a minimal defining set of D}. We show that if a t-( v, k, λ) design D is contained in a design F, then for every minimal defining set d D of D there exists a minimal defining set d F of F such that $${d_D = d_F\cap D}$$. The unique simple design with parameters $${{\left(v,k, {v-2\choose k-2}\right)}}$$ is said to be the full design on v elements; it comprises all possible k-tuples on a v set. Every simple t-( v, k, λ) design is contained in a full design, so studying minimal defining sets of full designs gives valuable information about the minimal defining sets of all t-( v, k, λ) designs. This paper studies the minimal defining sets of full designs when t = 2 and k = 3. Several families of non-isomorphic minimal defining sets of these designs are found. For given v, a lower bound on the size of the smallest and an upper bound on the size of the largest minimal defining set are given. The existence of a continuous section of the spectrum comprising approximately v values is shown, where just two values were known previously. [ABSTRACT FROM AUTHOR]

Tuza conjectured that if a simple graph G does not contain more than k pairwise edge-disjoint triangles, then there exists a set of at most 2 k edges that meets all triangles in G. It has been shown that this conjecture is true for planar graphs and the bound is sharp. In this paper, we characterize the set of extremal planar graphs. [ABSTRACT FROM AUTHOR]

A vertex subset S of a graph G = ( V, E) is a total dominating set if every vertex of G is adjacent to some vertex in S. The total domination number of G, denoted by γ t( G), is the minimum cardinality of a total dominating set of G. A graph G with no isolated vertex is said to be total domination vertex critical if for any vertex v of G that is not adjacent to a vertex of degree one, γ t( G− v) < γ t( G). A total domination vertex critical graph G is called k- γ t-critical if γ t( G) = k. In this paper we first show that every 3- γ t-critical graph G of even order has a perfect matching if it is K1,5-free. Secondly, we show that every 3- γ t-critical graph G of odd order is factor-critical if it is K1,5-free. Finally, we show that G has a perfect matching if G is a K1,4-free 4- γ t( G)-critical graph of even order and G is factor-critical if G is a K1,4-free 4- γ t( G)-critical graph of odd order. [ABSTRACT FROM AUTHOR]