# Browse

## You are looking at 1 - 10 of 604 items for :

• Discrete Mathematics
Clear All
Open access

## Abstract

The Turán number of a graph H, denoted by ex(n, H), is the maximum number of edges in any graph on n vertices which does not contain H as a subgraph. Let Pk denote the path on k vertices and let mPk denote m disjoint copies of Pk. Bushaw and Kettle [Turán numbers of multiple paths and equibipartite forests, Combin. Probab. Comput. 20 (2011) 837–853] determined the exact value of ex(n, kP) for large values of n. Yuan and Zhang [The Turán number of disjoint copies of paths, Discrete Math. 340 (2017) 132–139] completely determined the value of ex(n, kP 3) for all n, and also determined ex(n, Fm), where Fm is the disjoint union of m paths containing at most one odd path. They also determined the exact value of ex(n, P 3P 2 +1) for n ≥ 2 + 4. Recently, Bielak and Kieliszek [The Turán number of the graph 2P 5, Discuss. Math. Graph Theory 36 (2016) 683–694], Yuan and Zhang [Turán numbers for disjoint paths, arXiv:1611.00981v1] independently determined the exact value of ex(n, 2P 5). In this paper, we show that ex(n, 2P 7) = max{[n, 14, 7], 5n − 14} for all n ≥ 14, where [n, 14, 7] = (5n + 91 + r(r − 6))/2, n − 13 ≡ r (mod 6) and 0 ≤ r < 6.

Open access

## Abstract

A total Roman dominating function on a graph G is a labeling f : V (G) → {0, 1, 2} such that every vertex with label 0 has a neighbor with label 2 and the subgraph of G induced by the set of all vertices of positive weight has no isolated vertex. The minimum weight of a total Roman dominating function on a graph G is called the total Roman domination number of G. The total Roman reinforcement number rtR (G) of a graph G is the minimum number of edges that must be added to G in order to decrease the total Roman domination number. In this paper, we investigate the proper- ties of total Roman reinforcement number in graphs, and we present some sharp bounds for rtR (G). Moreover, we show that the decision problem for total Roman reinforcement is NP-hard for bipartite graphs.

Open access

## Abstract

A proper coloring of the vertices of a graph is called a star coloring if at least three colors are used on every 4-vertex path. We show that all outerplanar bipartite graphs can be star colored using only five colors and construct the smallest known example that requires five colors.

Open access

## Abstract

In this paper, we study the Hamiltonicity of graphs with large minimum degree. Firstly, we present some conditions for a simple graph to be Hamilton-connected and traceable from every vertex in terms of the spectral radius of the graph or its complement, respectively. Secondly, we give the conditions for a nearly balanced bipartite graph to be traceable in terms of spectral radius, signless Laplacian spectral radius of the graph or its quasi-complement, respectively.

Open access

## Abstract

The study of a graph theory model of certain telecommunications network problems lead to the concept of path-pairability, a variation of weak linkedness of graphs. A graph G is k-path-pairable if for any set of 2k distinct vertices, si, ti, 1 ≤ ik, there exist pairwise edge-disjoint si, t i-paths in G, for 1 ≤ ik. The path-pairability number is the largest k such that G is k-path-pairable. Cliques, stars, the Cartesian product of two cliques (of order at least three) are ‘fully pairable’; that is ⌊n/2⌋-pairable, where n is the order of the graph. Here we determine the path-pairability number of the Cartesian product of two stars.

Open access

## Abstract

For integers nk ≥ 2, let c(n, k) be the minimum number of chords that must be added to a cycle of length n so that the resulting graph has the property that for every l ∈ {k, k + 1, . . . , n}, there is a cycle of length l that contains exactly k of the added chords. Affif Chaouche, Rutherford, and Whitty introduced the function c(n, k). They showed that for every integer k ≥ 2, c(n, k) ≥ Ωk(n1/ k) and they asked if n 1/ k gives the correct order of magnitude of c(n, k) for k ≥ 2. Our main theorem answers this question as we prove that for every integer k ≥ 2, and for sufficiently large n, c(n, k) ≤ kn 1/ k⌉ + k 2. This upper bound, together with the lower bound of Affif Chaouche et al., shows that the order of magnitude of c(n, k) is n 1/ k.

Open access

## Abstract

A well-known theorem by Chvátal-Erdőos [A note on Hamilton circuits, Discrete Math. 2 (1972) 111–135] states that if the independence number of a graph G is at most its connectivity plus one, then G is traceable. In this article, we show that every 2-connected claw-free graph with independence number α(G) ≤ 6 is traceable or belongs to two exceptional families of well-defined graphs. As a corollary, we also show that every 2-connected claw-free graph with independence number α(G) ≤ 5 is traceable.

Open access

## Abstract

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, i(G), of G is the minimum cardinality of an independent dominating set. Goddard and Henning [Discrete Math. 313 (2013) 839–854] posed the conjecture that if G ∉ {K 3 , 3, C 5K 2} is a connected, cubic graph on n vertices, then $i(G)≤38n$, where C 5K 2 is the 5-prism. As an application of known result, we observe that this conjecture is true when G is 2-connected and planar, and we provide an infinite family of such graphs that achieve the bound. We conjecture that if G is a bipartite, planar, cubic graph of order n, then $i(G)≤13n$, and we provide an infinite family of such graphs that achieve this bound.

Open access

## Abstract

Let D be any of the 10 digraphs obtained by orienting the edges of K 4e. We establish necessary and sufficient conditions for the existence of a ($Kn*$, D)-design for 8 of these digraphs. Partial results as well as some nonexistence results are established for the remaining 2 digraphs.

Open access

## Abstract

We present some new constructive upper bounds based on product graphs for generalized vertex Folkman numbers. They lead to new upper bounds for some special cases of generalized edge Folkman numbers, including the cases F e(K 3, K 4e; K 5) ≤ 27 and F e(K 4e, K 4e; K 5) ≤ 51. The latter bound follows from a construction of a K 5-free graph on 51 vertices, for which every edge coloring with two colors contains a monochromatic K 4e.