Browse

You are looking at 81 - 90 of 92,054 items for

Open access

Radhika Ramamurthi and Gina Sanders

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

Guidong Yu, Yi Fang, Yizheng Fan and Gaixiang Cai

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

Adam S. Jobson, André. Kézdy, Jenő Lehel and Gábor Mészáros

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

Vladislav Taranchuk

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

Shipeng Wang and Liming Xiong

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

Gholamreza Abrishami, Michael A. Henning and Freydoon Rahbarnia

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

Ryan C. Bunge, Brian D. Darrow, Toni M. Dubczuk, Saad I. El-Zanati, Hanson H. Hao, Gregory L. Keller, Genevieve A. Newkirk and Dan P. Roberts

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

Xiaodong Xu, Meilian Liang and Stanisław Radziszowski

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.

Open access

Xueliang Li and Xiaoyu Zhu

Abstract

For an r-regular graph G, we define an edge-coloring c with colors from {1, 2, . . . , k}, in such a way that any vertex of G is incident with at least one edge of each color. The multiset-color cm(v) of a vertex v is defined as the ordered tuple (a 1, a 2, . . . , ak), where ai (1 ≤ ik) denotes the number of edges of color i which are incident with v in G. Then this edge-coloring c is called a k-kaleidoscopic coloring of G if every two distinct vertices in G have different multiset-colors and in this way the graph G is defined as a k-kaleidoscope. In this paper, we determine the integer k for a complete graph Kn to be a k-kaleidoscope, and hence solve a conjecture in [P. Zhang, A Kaleidoscopic View of Graph Colorings, (Springer Briefs in Math., New York, 2016)] that for any integers n and k with nk + 3 ≥ 6, the complete graph Kn is a k-kaleidoscope. Then, we construct an r-regular 3-kaleidoscope of order (2r-1)-1 − 1 for each integer r ≥ 7, where r ≡ 3 (mod 4), which solves another conjecture in [P. Zhang, A Kaleidoscopic View of Graph Colorings, (Springer Briefs in Math., New York, 2016)] on the maximum order of r-regular 3-kaleidoscopes.

Open access

Stanislav Jendroľ and Lucia Kekeňáková

Abstract

A vertex coloring of a plane graph G is a facial rainbow coloring if any two vertices of G connected by a facial path have distinct colors. The facial rainbow number of a plane graph G, denoted by rb(G), is the minimum number of colors that are necessary in any facial rainbow coloring of G. Let L(G) denote the order of a longest facial path in G. In the present note we prove that rb(T)32L(T) for any tree T and rb(G)53L(G) for arbitrary simple graph G. The upper bound for trees is tight. For any simple 3-connected plane graph G we have rb(G) ≤ L(G) + 5.