Issues

Journal & Issues

AHEAD OF PRINT

Volume 42 (2022): Issue 4 (November 2022)

Volume 42 (2022): Issue 3 (August 2022)

Volume 42 (2022): Issue 2 (May 2022)

Volume 42 (2022): Issue 1 (February 2022)

Volume 41 (2021): Issue 4 (November 2021)

Volume 41 (2021): Issue 3 (August 2021)

Volume 41 (2021): Issue 2 (May 2021)

Volume 41 (2021): Issue 1 (February 2021)

Volume 40 (2020): Issue 4 (November 2020)

Volume 40 (2020): Issue 3 (August 2020)

Volume 40 (2020): Issue 2 (May 2020)

Volume 40 (2020): Issue 1 (February 2020)

Volume 39 (2019): Issue 4 (November 2019)

Volume 39 (2019): Issue 3 (August 2019)

Volume 39 (2019): Issue 2 (May 2019)

Volume 39 (2019): Issue 1 (February 2019)

Volume 38 (2018): Issue 4 (November 2018)

Volume 38 (2018): Issue 3 (August 2018)

Volume 38 (2018): Issue 2 (May 2018)

Volume 38 (2018): Issue 1 (February 2018)

Volume 37 (2017): Issue 4 (November 2017)

Volume 37 (2017): Issue 3 (August 2017)

Volume 37 (2017): Issue 2 (May 2017)

Volume 37 (2017): Issue 1 (February 2017)

Volume 36 (2016): Issue 4 (November 2016)

Volume 36 (2016): Issue 3 (August 2016)

Volume 36 (2016): Issue 2 (May 2016)

Volume 36 (2016): Issue 1 (February 2016)

Volume 35 (2015): Issue 4 (November 2015)

Volume 35 (2015): Issue 3 (August 2015)

Volume 35 (2015): Issue 2 (May 2015)

Volume 35 (2015): Issue 1 (February 2015)

Volume 34 (2014): Issue 4 (November 2014)

Volume 34 (2014): Issue 3 (August 2014)

Volume 34 (2014): Issue 2 (May 2014)

Volume 34 (2014): Issue 1 (February 2014)

Volume 33 (2013): Issue 4 (November 2013)

Volume 33 (2013): Issue 3 (August 2013)

Volume 33 (2013): Issue 2 (May 2013)

Volume 33 (2013): Issue 1 (February 2013)

Journal Details
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English

Search

Volume 42 (2022): Issue 4 (November 2022)

Journal Details
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English

Search

20 Articles
access type Open Access

Distance-Local Rainbow Connection Number

Published Online: 12 Jul 2022
Page range: 1027 - 1039

Abstract

Abstract

Under an edge coloring (not necessarily proper), a rainbow path is a path whose edge colors are all distinct. The d-local rainbow connection number lrcd(G) (respectively, d-local strong rainbow connection number lsrcd(G)) is the smallest number of colors needed to color the edges of G such that any two vertices with distance at most d can be connected by a rainbow path (respectively, rainbow geodesic). This generalizes rainbow connection numbers, which are the special case d = diam(G). We discuss some bounds and exact values. Moreover, we also characterize all triples of positive integers d, a, b such that there is a connected graph G with lrcd(G) = a and lsrcd(G) = b.

Keywords

  • rainbow connection
  • chromatic number
  • line graph

MSC 2010

  • 05C15
  • 05C38
  • 05C40
access type Open Access

Flippable Edges in Triangulations on Surfaces

Published Online: 12 Jul 2022
Page range: 1041 - 1059

Abstract

Abstract

Concerning diagonal flips on triangulations, Gao et al. showed that any triangulation G on the sphere with n ≥ 5 vertices has at least n − 2 flippable edges. Furthermore, if G has minimum degree at least 4 and n ≥ 9, then G has at least 2n + 3 flippable edges. In this paper, we give a simpler proof of their results, and extend them to the case of the projective plane, the torus and the Klein bottle. Finally, we give an estimation for the number of flippable edges of a triangulation on general surfaces, using the notion of irreducible triangulations.

Keywords

  • triangulation
  • diagonal flip
  • surface

MSC 2010

  • 05C10
access type Open Access

Singular Turán Numbers and Worm-Colorings

Published Online: 12 Jul 2022
Page range: 1061 - 1074

Abstract

Abstract

A subgraph G of H is singular if the vertices of G either have the same degree in H or have pairwise distinct degrees in H. The largest number of edges of a graph on n vertices that does not contain a singular copy of G is denoted by TS(n, G). Caro and Tuza in [Singular Ramsey and Turán numbers, Theory Appl. Graphs 6 (2019) 1–32] obtained the asymptotics of TS(n, G) for every graph G, but determined the exact value of this function only in the case G = K3 and n ≡ 2 (mod 4). We determine TS(n, K3) for all n ≡ 0 (mod 4) and n ≡ 1 (mod 4), and also TS(n, Kr+1) for large enough n that is divisible by r.

We also explore the connection to the so-called G-WORM colorings (vertex colorings without rainbow or monochromatic copies of G) and obtain new results regarding the largest number of edges that a graph with a G-WORM coloring can have.

Keywords

  • Turán number
  • WORM-coloring
  • singular Turán numbers

MSC 2010

  • 05C35
  • 05D10
access type Open Access

On Mf-Edge Colorings of Graphs

Published Online: 12 Jul 2022
Page range: 1075 - 1088

Abstract

Abstract

An edge coloring φ of a graph G is called an Mf-edge coloring if | φ(v)| ≤ f(v) for every vertex v of G, where φ(v) is the set of colors of edges incident with v and f is a function which assigns a positive integer f(v) to each vertex v. Let 𝒦f (G) denote the maximum number of colors used in an Mf-edge coloring of G. In this paper we establish some bounds on 𝒦f(G), present some graphs achieving the bounds and determine exact values of 𝒦f(G) for some special classes of graphs.

Keywords

  • edge coloring
  • anti-Ramsey number
  • dominating set

MSC 2010

  • 05C15
access type Open Access

Decomposing 10-Regular Graphs into Paths of Length 5

Published Online: 12 Jul 2022
Page range: 1089 - 1097

Abstract

Abstract

Let G be a 10-regular graph which does not contain any 4-cycles. In this paper, we prove that G can be decomposed into paths of length 5, such that every vertex is a terminal of exactly two paths.

Keywords

  • 10-regular graph
  • decomposition
  • path

MSC 2010

  • 05C38
  • 05C70
access type Open Access

(C3, C4, C5, C7)-Free Almost Well-Dominated Graphs

Published Online: 12 Jul 2022
Page range: 1099 - 1117

Abstract

Abstract

The domination gap of a graph G is defined as the di erence between the maximum and minimum cardinalities of a minimal dominating set in G. The term well-dominated graphs referring to the graphs with domination gap zero, was first introduced by Finbow et al. [Well-dominated graphs: A collection of well-covered ones, Ars Combin. 25 (1988) 5–10]. In this paper, we focus on the graphs with domination gap one which we term almost well-dominated graphs. While the results by Finbow et al. have implications for almost well-dominated graphs with girth at least 8, we extend these results to (C3, C4, C5, C7)-free almost well-dominated graphs by giving a complete structural characterization for such graphs.

Keywords

  • well-dominated graphs
  • almost well-dominated graphs
  • domination gap

MSC 2010

  • 05C69
  • 05C75
  • 68R10
access type Open Access

The Turán Number for 4 · S1

Published Online: 12 Jul 2022
Page range: 1119 - 1128

Abstract

Abstract

The Turán number of a graph H, denoted by ex(n, H), is the maximum number of edges of an n-vertex simple graph having no H as a subgraph. Let S denote the star on + 1 vertices, and let k · S denote k disjoint copies of S. Erdős and Gallai determined the value ex(n, k · S1) for all positive integers k and n. Yuan and Zhang determined the value ex(n, k · S2) and characterized all extremal graphs for all positive integers k and n. Recently, Lan et al. determined the value ex(n, 2 · S3) for all positive integers n, and Li and Yin determined the values ex(n, k · S) for k = 2, 3 and all positive integers and n. In this paper, we further determine the value ex(n, 4 · S) for all positive integers and almost all n, improving one of the results of Lidický et al.

Keywords

  • Turán number
  • disjoint copies
  • ·

MSC 2010

  • 05C35
access type Open Access

Bounds on the Double Italian Domination Number of a Graph

Published Online: 12 Jul 2022
Page range: 1129 - 1137

Abstract

Abstract

For a graph G, a Roman {3}-dominating function is a function f : V → {0, 1, 2, 3} having the property that for every vertex uV, if f(u) ∈ {0, 1}, then f(N[u]) ≥ 3. The weight of a Roman {3}-dominating function is the sum w(f) = f(V) = ΣvV f(v), and the minimum weight of a Roman {3}-dominating function is the Roman {3}-domination number, denoted by γ{R3}(G). In this paper, we present a sharp lower bound for the double Italian domination number of a graph, and improve previous bounds given in [D.A. Mojdeh and L. Volkmann, Roman {3}-domination (double Italian domination), Discrete Appl. Math. 283 (2022) 555–564]. We also present a probabilistic upper bound for a generalized version of double Italian domination number of a graph, and show that the given bound is asymptotically best possible.

Keywords

  • Italian domination
  • double Italian domination
  • probabilistic methods

MSC 2010

  • 05C69
access type Open Access

Finding Dominating Induced Matchings in P9-Free Graphs in Polynomial Time

Published Online: 12 Jul 2022
Page range: 1139 - 1162

Abstract

Abstract

Let G = (V, E) be a finite undirected graph. An edge subset E′ ⊆ E is a dominating induced matching (d.i.m.) in G if every edge in E is intersected by exactly one edge of E′. The Dominating Induced Matching (DIM) problem asks for the existence of a d.i.m. in G. The DIM problem is 𝕅𝕇-complete even for very restricted graph classes such as planar bipartite graphs with maximum degree 3 but was solved in linear time for P7-free graphs and in polynomial time for P8-free graphs. In this paper, we solve it in polynomial time for P9-free graphs.

Keywords

  • dominating induced matching
  • -free graphs
  • polynomial time algorithm

MSC 2010

  • 05C69
  • 68R10
access type Open Access

Cyclic Permutations in Determining Crossing Numbers

Published Online: 12 Jul 2022
Page range: 1163 - 1183

Abstract

Abstract

The crossing number of a graph G is the minimum number of edge crossings over all drawings of G in the plane. Recently, the crossing numbers of join products of two graphs have been studied. In the paper, we extend know results concerning crossing numbers of join products of small graphs with discrete graphs. The crossing number of the join product G*+ Dn for the disconnected graph G* consisting of five vertices and of three edges incident with the same vertex is given. Up to now, the crossing numbers of G + Dn were done only for connected graphs G. In the paper also the crossing numbers of G*+ Pn and G* + Cn are given. The paper concludes by giving the crossing numbers of the graphs H + Dn, H + Pn, and H + Cn for four different graphs H with |E(H)| ≤ |V (H)|. The methods used in the paper are new. They are based on combinatorial properties of cyclic permutations.

Keywords

  • graph
  • drawing
  • crossing number
  • join product
  • cyclic permutation

MSC 2010

  • 05C10
  • 05C38
access type Open Access

More on the Rainbow Disconnection in Graphs

Published Online: 12 Jul 2022
Page range: 1185 - 1204

Abstract

Abstract

Let G be a nontrivial edge-colored connected graph. An edge-cut R of G is called a rainbow-cut if no two of its edges are colored the same. An edge-colored graph G is rainbow disconnected if for every two vertices u and v of G, there exists a u-v-rainbow-cut separating them. For a connected graph G, the rainbow disconnection number of G, denoted by rd(G), is defined as the smallest number of colors that are needed in order to make G rainbow disconnected. In this paper, we first determine the maximum size of a connected graph G of order n with rd(G) = k for any given integers k and n with 1 ≤ kn − 1, which solves a conjecture posed only for n odd in [G. Chartrand, S. Devereaux, T.W. Haynes, S.T. Hedetniemi and P. Zhang, Rainbow disconnection in graphs, Discuss. Math. Graph Theory 38 (2018) 1007–1021]. From this result and a result in their paper, we obtain Erdős-Gallai type results for rd(G). Secondly, we discuss bounds on rd(G) for complete multipartite graphs, critical graphs with respect to the chromatic number, minimal graphs with respect to the chromatic index, and regular graphs, and we also give the values of rd(G) for several special graphs. Thirdly, we get Nordhaus-Gaddum type bounds for rd(G), and examples are given to show that the upper and lower bounds are sharp. Finally, we show that for a connected graph G, to compute rd(G) is NP-hard. In particular, we show that it is already NP-complete to decide if rd(G) = 3 for a connected cubic graph. Moreover, we show that for a given edge-colored (with an unbounded number of colors) connected graph G it is NP-complete to decide whether G is rainbow disconnected.

Keywords

  • edge-coloring
  • edge-connectivity
  • rainbow disconnection coloring (number)
  • Erdős-Gallai type problem
  • Nordhaus-Gaddum type bounds
  • complexity
  • NP-hard (complete)

MSC 2010

  • 05C15
  • 05C40
  • 05C35
  • 68Q17
  • 68Q25
  • 68R10
access type Open Access

Antimagic Labeling of Some Biregular Bipartite Graphs

Published Online: 12 Jul 2022
Page range: 1205 - 1218

Abstract

Abstract

An antimagic labeling of a graph G = (V, E) is a one-to-one mapping from E to {1, 2, . . ., |E|} such that distinct vertices receive different label sums from the edges incident to them. G is called antimagic if it admits an antimagic labeling. It was conjectured that every connected graph other than K2 is antimagic. The conjecture remains open though it was verified for several classes of graphs such as regular graphs. A bipartite graph is called (k, k′)-biregular, if each vertex of one of its parts has the degree k, while each vertex of the other parts has the degree k′. This paper shows the following results. (1) Each connected (2, k)-biregular (k ≥ 3) bipartite graph is antimagic; (2) Each (k, pk)-biregular (k ≥ 3, p ≥ 2) bipartite graph is antimagic; (3) Each (k, k2 + y)-biregular (k ≥ 3, y ≥ 1) bipartite graph is antimagic.

Keywords

  • antimagic labeling
  • bipartite
  • biregular

MSC 2010

  • 05C69
access type Open Access

On Small Balanceable, Strongly-Balanceable and Omnitonal Graphs

Published Online: 12 Jul 2022
Page range: 1219 - 1235

Abstract

Abstract

In Ramsey Theory for graphs we are given a graph G and we are required to find the least n0 such that, for any nn0, any red/blue colouring of the edges of Kn gives a subgraph G all of whose edges are blue or all are red. Here we shall be requiring that, for any red/blue colouring of the edges of Kn, there must be a copy of G such that its edges are partitioned equally as red or blue (or the sizes of the colour classes differs by one in the case when G has an odd number of edges). This introduces the notion of balanceable graphs and the balance number of G which, if it exists, is the minimum integer bal(n, G) such that, for any red/blue colouring of E(Kn) with more than bal(n, G) edges of either colour, Kn will contain a balanced coloured copy of G as described above. The strong balance number sbal(n, G) is analogously defined when G has an odd number of edges, but in this case we require that there are copies of G with both one more red edge and one more blue edge.

These parameters were introduced by Caro, Hansberg and Montejano. These authors also introduce the more general omnitonal number ot(n, G) which requires copies of G containing a complete distribution of the number of red and blue edges over E(G).

In this paper we shall catalogue bal(n, G), sbal(n, G) and ot(n, G) for all graphs G on at most four edges. We shall be using some of the key results of Caro et al. which we here reproduce in full, as well as some new results which we prove here. For example, we shall prove that the union of two bipartite graphs with the same number of edges is always balanceable.

Keywords

  • edge-colouring
  • zero-sum Ramsey
  • balanceable graphs
  • omnitonal graphs

MSC 2010

  • 05C15
  • 05C55
access type Open Access

More Aspects of Arbitrarily Partitionable Graphs

Published Online: 12 Jul 2022
Page range: 1237 - 1261

Abstract

Abstract

A graph G of order n is arbitrarily partitionable (AP) if, for every sequence (n1, . . ., np) partitioning n, there is a partition (V1, . . ., ,Vp) of V (G) such that G[Vi] is a connected ni-graph for i = 1, . . ., p. The property of being AP is related to other well-known graph notions, such as perfect matchings and Hamiltonian cycles, with which it shares several properties. This work is dedicated to studying two aspects behind AP graphs.

On the one hand, we consider algorithmic aspects of AP graphs, which received some attention in previous works. We first establish the NP-hardness of the problem of partitioning a graph into connected subgraphs following a given sequence, for various new graph classes of interest. We then prove that the problem of deciding whether a graph is AP is in NP for several classes of graphs, confirming a conjecture of Barth and Fournier for these.

On the other hand, we consider the weakening to APness of su cient conditions for Hamiltonicity. While previous works have suggested that such conditions can sometimes indeed be weakened, we here point out cases where this is not true. This is done by considering conditions for Hamiltonicity involving squares of graphs, and claw- and net-free graphs.

Keywords

  • arbitrarily partitionable graphs
  • partition into connected subgraphs
  • Hamiltonicity

MSC 2010

  • 05C15
  • 05C40
  • 05C69
  • 68R10
access type Open Access

Representing Split Graphs by Words

Published Online: 12 Jul 2022
Page range: 1263 - 1280

Abstract

Abstract

There is a long line of research in the literature dedicated to word-representable graphs, which generalize several important classes of graphs. However, not much is known about word-representability of split graphs, another important class of graphs.

In this paper, we show that threshold graphs, a subclass of split graphs, are word-representable. Further, we prove a number of general theorems on word-representable split graphs, and use them to characterize computationally such graphs with cliques of size 5 in terms of nine forbidden subgraphs, thus extending the known characterization for word-representable split graphs with cliques of size 4. Moreover, we use split graphs, and also provide an alternative solution, to show that gluing two word-representable graphs in any clique of size at least 2 may, or may not, result in a word-representable graph. The two surprisingly simple solutions provided by us answer a question that was open for about ten years.

Keywords

  • split graph
  • word-representability
  • semi-transitive orientation

MSC 2010

  • 05C62
access type Open Access

Nested Locally Hamiltonian Graphs and the Oberly-Sumner Conjecture

Published Online: 12 Jul 2022
Page range: 1281 - 1312

Abstract

Abstract

A graph G is locally 𝒫, abbreviated L𝒫, if for every vertex v in G the open neighbourhood N(v) of v is non-empty and induces a graph with property 𝒫. Specifically, a graph G without isolated vertices is locally connected (LC) if N(v) induces a connected graph for each vV (G), and locally hamiltonian (LH) if N(v) induces a hamiltonian graph for each vV (G). A graph G is locally locally 𝒫 (abbreviated L2𝒫) if N(v) is non-empty and induces a locally 𝒫 graph for every vV (G). This concept is generalized to an arbitrary degree of nesting. For any k 0 we call a graph locally k-nested-hamiltonian if it is LmC for m = 0, 1, . . ., k and LkH (with L0C and L0H meaning connected and hamiltonian, respectively). The class of locally k-nested-hamiltonian graphs contains important subclasses. For example, Skupień had already observed in 1963 that the class of connected LH graphs (which is the class of locally 1-nested-hamiltonian graphs) contains all triangulations of closed surfaces. We show that for any k ≥ 1 the class of locally k-nested-hamiltonian graphs contains all simple-clique (k + 2)-trees. In 1979 Oberly and Sumner proved that every connected K1,3-free graph that is locally connected is hamiltonian. They conjectured that for k ≥ 1, every connected K1,k+3-free graph that is locally (k + 1)-connected is hamiltonian. We show that locally k-nested-hamiltonian graphs are locally (k + 1)-connected and consider the weaker conjecture that every K1,k+3-free graph that is locally k-nested-hamiltonian is hamiltonian. We show that if our conjecture is true, it would be “best possible” in the sense that for every k ≥ 1 there exist K1,k+4-free locally k-nested-hamiltonian graphs that are non-hamiltonian. We also attempt to determine the minimum order of non-hamiltonian locally k-nested-hamiltonian graphs and investigate the complexity of the Hamilton Cycle Problem for locally k-nested-hamiltonian graphs with restricted maximum degree.

Keywords

  • locally traceable
  • locally hamiltonian
  • Hamilton Cycle Problem
  • locally -nested-hamiltonian
  • Oberly-Sumner Conjecture

MSC 2010

  • 05C60
access type Open Access

More on Signed Graphs with at Most Three Eigenvalues

Published Online: 12 Jul 2022
Page range: 1313 - 1331

Abstract

Abstract

We consider signed graphs with just 2 or 3 distinct eigenvalues, in particular (i) those with at least one simple eigenvalue, and (ii) those with vertex-deleted subgraphs which themselves have at most 3 distinct eigenvalues. We also construct new examples using weighing matrices and symmetric 3-class association schemes.

Keywords

  • adjacency matrix
  • simple eigenvalue
  • strongly regular signed graph
  • vertex-deleted subgraph
  • weighing matrix
  • association scheme

MSC 2010

  • 05C22
  • 05C50
access type Open Access

Covering the Edges of a Random Hypergraph by Cliques

Published Online: 12 Jul 2022
Page range: 1333 - 1349

Abstract

Abstract

We determine the order of magnitude of the minimum clique cover of the edges of a binomial, r-uniform, random hypergraph G(r)(n, p), p fixed. In doing so, we combine the ideas from the proofs of the graph case (r = 2) in Frieze and Reed [Covering the edges of a random graph by cliques, Combinatorica 15 (1995) 489–497] and Guo, Patten, Warnke [Prague dimension of random graphs, manuscript submitted for publication].

Keywords

  • r-uniform random hypergraph
  • clique covering

MSC 2010

  • 05C65
  • 05C80
  • 05C62
  • 05C69
  • 05C70
  • 05C75
access type Open Access

On Singular Signed Graphs with Nullspace Spanned by a Full Vector: Signed Nut Graphs

Published Online: 12 Jul 2022
Page range: 1351 - 1382

Abstract

Abstract

A signed graph has edge weights drawn from the set {+1, −1}, and is sign-balanced if it is equivalent to an unsigned graph under the operation of sign switching; otherwise it is sign-unbalanced. A nut graph has a one dimensional kernel of the 0-1 adjacency matrix with a corresponding eigenvector that is full. In this paper we generalise the notion of nut graphs to signed graphs. Orders for which regular nut graphs with all edge weights +1 exist have been determined recently for the degrees up to 12. By extending the definition to signed graphs, we here find all pairs (ρ, n) for which a ρ-regular nut graph (sign-balanced or sign-unbalanced) of order n exists with ρ ≤ 11. We devise a construction for signed nut graphs based on a smaller ‘seed’ graph, giving infinite series of both sign-balanced and sign-unbalanced ρ -regular nut graphs. Orders for which a regular nut graph with ρ = n − 1 exists are characterised; they are sign-unbalanced with an underlying graph Kn for which n ≡ 1 (mod 4). Orders for which a regular sign-unbalanced nut graph with ρ = n − 2 exists are also characterised; they have an underlying cocktail-party graph CP(n) with even order n ≥ 8.

Keywords

  • signed graph
  • nut graph
  • singular graph
  • graph spectrum
  • Fowler construction
  • sign-balanced graph
  • sign-unbalanced graph
  • cocktail-party graph

MSC 2010

  • 05C50
  • 15A18
  • 05C22
  • 05C92
access type Open Access

A Note on Packing of Uniform Hypergraphs

Published Online: 12 Jul 2022
Page range: 1383 - 1388

Abstract

Abstract

We say that two n-vertex hypergraphs H1 and H2 pack if they can be found as edge-disjoint subhypergraphs of the complete hypergraph Kn. Whilst the problem of packing of graphs (i.e., 2-uniform hypergraphs) has been studied extensively since seventies, much less is known about packing of k-uniform hypergraphs for k ≥ 3. Naroski [Packing of nonuniform hypergraphs - product and sum of sizes conditions, Discuss. Math. Graph Theory 29 (2009) 651–656] defined the parameter mk(n) to be the smallest number m such that there exist two n-vertex k-uniform hypergraphs with total number of edges equal to m which do not pack, and conjectured that mk(n) = Θ (nk−1). In this note we show that this conjecture is far from being truth. Namely, we prove that the growth rate of mk(n) is of order nk/2 exactly for even k’s and asymptotically for odd k’s.

Keywords

  • packing
  • hypergraphs

MSC 2010

  • 05C35
20 Articles
access type Open Access

Distance-Local Rainbow Connection Number

Published Online: 12 Jul 2022
Page range: 1027 - 1039

Abstract

Abstract

Under an edge coloring (not necessarily proper), a rainbow path is a path whose edge colors are all distinct. The d-local rainbow connection number lrcd(G) (respectively, d-local strong rainbow connection number lsrcd(G)) is the smallest number of colors needed to color the edges of G such that any two vertices with distance at most d can be connected by a rainbow path (respectively, rainbow geodesic). This generalizes rainbow connection numbers, which are the special case d = diam(G). We discuss some bounds and exact values. Moreover, we also characterize all triples of positive integers d, a, b such that there is a connected graph G with lrcd(G) = a and lsrcd(G) = b.

Keywords

  • rainbow connection
  • chromatic number
  • line graph

MSC 2010

  • 05C15
  • 05C38
  • 05C40
access type Open Access

Flippable Edges in Triangulations on Surfaces

Published Online: 12 Jul 2022
Page range: 1041 - 1059

Abstract

Abstract

Concerning diagonal flips on triangulations, Gao et al. showed that any triangulation G on the sphere with n ≥ 5 vertices has at least n − 2 flippable edges. Furthermore, if G has minimum degree at least 4 and n ≥ 9, then G has at least 2n + 3 flippable edges. In this paper, we give a simpler proof of their results, and extend them to the case of the projective plane, the torus and the Klein bottle. Finally, we give an estimation for the number of flippable edges of a triangulation on general surfaces, using the notion of irreducible triangulations.

Keywords

  • triangulation
  • diagonal flip
  • surface

MSC 2010

  • 05C10
access type Open Access

Singular Turán Numbers and Worm-Colorings

Published Online: 12 Jul 2022
Page range: 1061 - 1074

Abstract

Abstract

A subgraph G of H is singular if the vertices of G either have the same degree in H or have pairwise distinct degrees in H. The largest number of edges of a graph on n vertices that does not contain a singular copy of G is denoted by TS(n, G). Caro and Tuza in [Singular Ramsey and Turán numbers, Theory Appl. Graphs 6 (2019) 1–32] obtained the asymptotics of TS(n, G) for every graph G, but determined the exact value of this function only in the case G = K3 and n ≡ 2 (mod 4). We determine TS(n, K3) for all n ≡ 0 (mod 4) and n ≡ 1 (mod 4), and also TS(n, Kr+1) for large enough n that is divisible by r.

We also explore the connection to the so-called G-WORM colorings (vertex colorings without rainbow or monochromatic copies of G) and obtain new results regarding the largest number of edges that a graph with a G-WORM coloring can have.

Keywords

  • Turán number
  • WORM-coloring
  • singular Turán numbers

MSC 2010

  • 05C35
  • 05D10
access type Open Access

On Mf-Edge Colorings of Graphs

Published Online: 12 Jul 2022
Page range: 1075 - 1088

Abstract

Abstract

An edge coloring φ of a graph G is called an Mf-edge coloring if | φ(v)| ≤ f(v) for every vertex v of G, where φ(v) is the set of colors of edges incident with v and f is a function which assigns a positive integer f(v) to each vertex v. Let 𝒦f (G) denote the maximum number of colors used in an Mf-edge coloring of G. In this paper we establish some bounds on 𝒦f(G), present some graphs achieving the bounds and determine exact values of 𝒦f(G) for some special classes of graphs.

Keywords

  • edge coloring
  • anti-Ramsey number
  • dominating set

MSC 2010

  • 05C15
access type Open Access

Decomposing 10-Regular Graphs into Paths of Length 5

Published Online: 12 Jul 2022
Page range: 1089 - 1097

Abstract

Abstract

Let G be a 10-regular graph which does not contain any 4-cycles. In this paper, we prove that G can be decomposed into paths of length 5, such that every vertex is a terminal of exactly two paths.

Keywords

  • 10-regular graph
  • decomposition
  • path

MSC 2010

  • 05C38
  • 05C70
access type Open Access

(C3, C4, C5, C7)-Free Almost Well-Dominated Graphs

Published Online: 12 Jul 2022
Page range: 1099 - 1117

Abstract

Abstract

The domination gap of a graph G is defined as the di erence between the maximum and minimum cardinalities of a minimal dominating set in G. The term well-dominated graphs referring to the graphs with domination gap zero, was first introduced by Finbow et al. [Well-dominated graphs: A collection of well-covered ones, Ars Combin. 25 (1988) 5–10]. In this paper, we focus on the graphs with domination gap one which we term almost well-dominated graphs. While the results by Finbow et al. have implications for almost well-dominated graphs with girth at least 8, we extend these results to (C3, C4, C5, C7)-free almost well-dominated graphs by giving a complete structural characterization for such graphs.

Keywords

  • well-dominated graphs
  • almost well-dominated graphs
  • domination gap

MSC 2010

  • 05C69
  • 05C75
  • 68R10
access type Open Access

The Turán Number for 4 · S1

Published Online: 12 Jul 2022
Page range: 1119 - 1128

Abstract

Abstract

The Turán number of a graph H, denoted by ex(n, H), is the maximum number of edges of an n-vertex simple graph having no H as a subgraph. Let S denote the star on + 1 vertices, and let k · S denote k disjoint copies of S. Erdős and Gallai determined the value ex(n, k · S1) for all positive integers k and n. Yuan and Zhang determined the value ex(n, k · S2) and characterized all extremal graphs for all positive integers k and n. Recently, Lan et al. determined the value ex(n, 2 · S3) for all positive integers n, and Li and Yin determined the values ex(n, k · S) for k = 2, 3 and all positive integers and n. In this paper, we further determine the value ex(n, 4 · S) for all positive integers and almost all n, improving one of the results of Lidický et al.

Keywords

  • Turán number
  • disjoint copies
  • ·

MSC 2010

  • 05C35
access type Open Access

Bounds on the Double Italian Domination Number of a Graph

Published Online: 12 Jul 2022
Page range: 1129 - 1137

Abstract

Abstract

For a graph G, a Roman {3}-dominating function is a function f : V → {0, 1, 2, 3} having the property that for every vertex uV, if f(u) ∈ {0, 1}, then f(N[u]) ≥ 3. The weight of a Roman {3}-dominating function is the sum w(f) = f(V) = ΣvV f(v), and the minimum weight of a Roman {3}-dominating function is the Roman {3}-domination number, denoted by γ{R3}(G). In this paper, we present a sharp lower bound for the double Italian domination number of a graph, and improve previous bounds given in [D.A. Mojdeh and L. Volkmann, Roman {3}-domination (double Italian domination), Discrete Appl. Math. 283 (2022) 555–564]. We also present a probabilistic upper bound for a generalized version of double Italian domination number of a graph, and show that the given bound is asymptotically best possible.

Keywords

  • Italian domination
  • double Italian domination
  • probabilistic methods

MSC 2010

  • 05C69
access type Open Access

Finding Dominating Induced Matchings in P9-Free Graphs in Polynomial Time

Published Online: 12 Jul 2022
Page range: 1139 - 1162

Abstract

Abstract

Let G = (V, E) be a finite undirected graph. An edge subset E′ ⊆ E is a dominating induced matching (d.i.m.) in G if every edge in E is intersected by exactly one edge of E′. The Dominating Induced Matching (DIM) problem asks for the existence of a d.i.m. in G. The DIM problem is 𝕅𝕇-complete even for very restricted graph classes such as planar bipartite graphs with maximum degree 3 but was solved in linear time for P7-free graphs and in polynomial time for P8-free graphs. In this paper, we solve it in polynomial time for P9-free graphs.

Keywords

  • dominating induced matching
  • -free graphs
  • polynomial time algorithm

MSC 2010

  • 05C69
  • 68R10
access type Open Access

Cyclic Permutations in Determining Crossing Numbers

Published Online: 12 Jul 2022
Page range: 1163 - 1183

Abstract

Abstract

The crossing number of a graph G is the minimum number of edge crossings over all drawings of G in the plane. Recently, the crossing numbers of join products of two graphs have been studied. In the paper, we extend know results concerning crossing numbers of join products of small graphs with discrete graphs. The crossing number of the join product G*+ Dn for the disconnected graph G* consisting of five vertices and of three edges incident with the same vertex is given. Up to now, the crossing numbers of G + Dn were done only for connected graphs G. In the paper also the crossing numbers of G*+ Pn and G* + Cn are given. The paper concludes by giving the crossing numbers of the graphs H + Dn, H + Pn, and H + Cn for four different graphs H with |E(H)| ≤ |V (H)|. The methods used in the paper are new. They are based on combinatorial properties of cyclic permutations.

Keywords

  • graph
  • drawing
  • crossing number
  • join product
  • cyclic permutation

MSC 2010

  • 05C10
  • 05C38
access type Open Access

More on the Rainbow Disconnection in Graphs

Published Online: 12 Jul 2022
Page range: 1185 - 1204

Abstract

Abstract

Let G be a nontrivial edge-colored connected graph. An edge-cut R of G is called a rainbow-cut if no two of its edges are colored the same. An edge-colored graph G is rainbow disconnected if for every two vertices u and v of G, there exists a u-v-rainbow-cut separating them. For a connected graph G, the rainbow disconnection number of G, denoted by rd(G), is defined as the smallest number of colors that are needed in order to make G rainbow disconnected. In this paper, we first determine the maximum size of a connected graph G of order n with rd(G) = k for any given integers k and n with 1 ≤ kn − 1, which solves a conjecture posed only for n odd in [G. Chartrand, S. Devereaux, T.W. Haynes, S.T. Hedetniemi and P. Zhang, Rainbow disconnection in graphs, Discuss. Math. Graph Theory 38 (2018) 1007–1021]. From this result and a result in their paper, we obtain Erdős-Gallai type results for rd(G). Secondly, we discuss bounds on rd(G) for complete multipartite graphs, critical graphs with respect to the chromatic number, minimal graphs with respect to the chromatic index, and regular graphs, and we also give the values of rd(G) for several special graphs. Thirdly, we get Nordhaus-Gaddum type bounds for rd(G), and examples are given to show that the upper and lower bounds are sharp. Finally, we show that for a connected graph G, to compute rd(G) is NP-hard. In particular, we show that it is already NP-complete to decide if rd(G) = 3 for a connected cubic graph. Moreover, we show that for a given edge-colored (with an unbounded number of colors) connected graph G it is NP-complete to decide whether G is rainbow disconnected.

Keywords

  • edge-coloring
  • edge-connectivity
  • rainbow disconnection coloring (number)
  • Erdős-Gallai type problem
  • Nordhaus-Gaddum type bounds
  • complexity
  • NP-hard (complete)

MSC 2010

  • 05C15
  • 05C40
  • 05C35
  • 68Q17
  • 68Q25
  • 68R10
access type Open Access

Antimagic Labeling of Some Biregular Bipartite Graphs

Published Online: 12 Jul 2022
Page range: 1205 - 1218

Abstract

Abstract

An antimagic labeling of a graph G = (V, E) is a one-to-one mapping from E to {1, 2, . . ., |E|} such that distinct vertices receive different label sums from the edges incident to them. G is called antimagic if it admits an antimagic labeling. It was conjectured that every connected graph other than K2 is antimagic. The conjecture remains open though it was verified for several classes of graphs such as regular graphs. A bipartite graph is called (k, k′)-biregular, if each vertex of one of its parts has the degree k, while each vertex of the other parts has the degree k′. This paper shows the following results. (1) Each connected (2, k)-biregular (k ≥ 3) bipartite graph is antimagic; (2) Each (k, pk)-biregular (k ≥ 3, p ≥ 2) bipartite graph is antimagic; (3) Each (k, k2 + y)-biregular (k ≥ 3, y ≥ 1) bipartite graph is antimagic.

Keywords

  • antimagic labeling
  • bipartite
  • biregular

MSC 2010

  • 05C69
access type Open Access

On Small Balanceable, Strongly-Balanceable and Omnitonal Graphs

Published Online: 12 Jul 2022
Page range: 1219 - 1235

Abstract

Abstract

In Ramsey Theory for graphs we are given a graph G and we are required to find the least n0 such that, for any nn0, any red/blue colouring of the edges of Kn gives a subgraph G all of whose edges are blue or all are red. Here we shall be requiring that, for any red/blue colouring of the edges of Kn, there must be a copy of G such that its edges are partitioned equally as red or blue (or the sizes of the colour classes differs by one in the case when G has an odd number of edges). This introduces the notion of balanceable graphs and the balance number of G which, if it exists, is the minimum integer bal(n, G) such that, for any red/blue colouring of E(Kn) with more than bal(n, G) edges of either colour, Kn will contain a balanced coloured copy of G as described above. The strong balance number sbal(n, G) is analogously defined when G has an odd number of edges, but in this case we require that there are copies of G with both one more red edge and one more blue edge.

These parameters were introduced by Caro, Hansberg and Montejano. These authors also introduce the more general omnitonal number ot(n, G) which requires copies of G containing a complete distribution of the number of red and blue edges over E(G).

In this paper we shall catalogue bal(n, G), sbal(n, G) and ot(n, G) for all graphs G on at most four edges. We shall be using some of the key results of Caro et al. which we here reproduce in full, as well as some new results which we prove here. For example, we shall prove that the union of two bipartite graphs with the same number of edges is always balanceable.

Keywords

  • edge-colouring
  • zero-sum Ramsey
  • balanceable graphs
  • omnitonal graphs

MSC 2010

  • 05C15
  • 05C55
access type Open Access

More Aspects of Arbitrarily Partitionable Graphs

Published Online: 12 Jul 2022
Page range: 1237 - 1261

Abstract

Abstract

A graph G of order n is arbitrarily partitionable (AP) if, for every sequence (n1, . . ., np) partitioning n, there is a partition (V1, . . ., ,Vp) of V (G) such that G[Vi] is a connected ni-graph for i = 1, . . ., p. The property of being AP is related to other well-known graph notions, such as perfect matchings and Hamiltonian cycles, with which it shares several properties. This work is dedicated to studying two aspects behind AP graphs.

On the one hand, we consider algorithmic aspects of AP graphs, which received some attention in previous works. We first establish the NP-hardness of the problem of partitioning a graph into connected subgraphs following a given sequence, for various new graph classes of interest. We then prove that the problem of deciding whether a graph is AP is in NP for several classes of graphs, confirming a conjecture of Barth and Fournier for these.

On the other hand, we consider the weakening to APness of su cient conditions for Hamiltonicity. While previous works have suggested that such conditions can sometimes indeed be weakened, we here point out cases where this is not true. This is done by considering conditions for Hamiltonicity involving squares of graphs, and claw- and net-free graphs.

Keywords

  • arbitrarily partitionable graphs
  • partition into connected subgraphs
  • Hamiltonicity

MSC 2010

  • 05C15
  • 05C40
  • 05C69
  • 68R10
access type Open Access

Representing Split Graphs by Words

Published Online: 12 Jul 2022
Page range: 1263 - 1280

Abstract

Abstract

There is a long line of research in the literature dedicated to word-representable graphs, which generalize several important classes of graphs. However, not much is known about word-representability of split graphs, another important class of graphs.

In this paper, we show that threshold graphs, a subclass of split graphs, are word-representable. Further, we prove a number of general theorems on word-representable split graphs, and use them to characterize computationally such graphs with cliques of size 5 in terms of nine forbidden subgraphs, thus extending the known characterization for word-representable split graphs with cliques of size 4. Moreover, we use split graphs, and also provide an alternative solution, to show that gluing two word-representable graphs in any clique of size at least 2 may, or may not, result in a word-representable graph. The two surprisingly simple solutions provided by us answer a question that was open for about ten years.

Keywords

  • split graph
  • word-representability
  • semi-transitive orientation

MSC 2010

  • 05C62
access type Open Access

Nested Locally Hamiltonian Graphs and the Oberly-Sumner Conjecture

Published Online: 12 Jul 2022
Page range: 1281 - 1312

Abstract

Abstract

A graph G is locally 𝒫, abbreviated L𝒫, if for every vertex v in G the open neighbourhood N(v) of v is non-empty and induces a graph with property 𝒫. Specifically, a graph G without isolated vertices is locally connected (LC) if N(v) induces a connected graph for each vV (G), and locally hamiltonian (LH) if N(v) induces a hamiltonian graph for each vV (G). A graph G is locally locally 𝒫 (abbreviated L2𝒫) if N(v) is non-empty and induces a locally 𝒫 graph for every vV (G). This concept is generalized to an arbitrary degree of nesting. For any k 0 we call a graph locally k-nested-hamiltonian if it is LmC for m = 0, 1, . . ., k and LkH (with L0C and L0H meaning connected and hamiltonian, respectively). The class of locally k-nested-hamiltonian graphs contains important subclasses. For example, Skupień had already observed in 1963 that the class of connected LH graphs (which is the class of locally 1-nested-hamiltonian graphs) contains all triangulations of closed surfaces. We show that for any k ≥ 1 the class of locally k-nested-hamiltonian graphs contains all simple-clique (k + 2)-trees. In 1979 Oberly and Sumner proved that every connected K1,3-free graph that is locally connected is hamiltonian. They conjectured that for k ≥ 1, every connected K1,k+3-free graph that is locally (k + 1)-connected is hamiltonian. We show that locally k-nested-hamiltonian graphs are locally (k + 1)-connected and consider the weaker conjecture that every K1,k+3-free graph that is locally k-nested-hamiltonian is hamiltonian. We show that if our conjecture is true, it would be “best possible” in the sense that for every k ≥ 1 there exist K1,k+4-free locally k-nested-hamiltonian graphs that are non-hamiltonian. We also attempt to determine the minimum order of non-hamiltonian locally k-nested-hamiltonian graphs and investigate the complexity of the Hamilton Cycle Problem for locally k-nested-hamiltonian graphs with restricted maximum degree.

Keywords

  • locally traceable
  • locally hamiltonian
  • Hamilton Cycle Problem
  • locally -nested-hamiltonian
  • Oberly-Sumner Conjecture

MSC 2010

  • 05C60
access type Open Access

More on Signed Graphs with at Most Three Eigenvalues

Published Online: 12 Jul 2022
Page range: 1313 - 1331

Abstract

Abstract

We consider signed graphs with just 2 or 3 distinct eigenvalues, in particular (i) those with at least one simple eigenvalue, and (ii) those with vertex-deleted subgraphs which themselves have at most 3 distinct eigenvalues. We also construct new examples using weighing matrices and symmetric 3-class association schemes.

Keywords

  • adjacency matrix
  • simple eigenvalue
  • strongly regular signed graph
  • vertex-deleted subgraph
  • weighing matrix
  • association scheme

MSC 2010

  • 05C22
  • 05C50
access type Open Access

Covering the Edges of a Random Hypergraph by Cliques

Published Online: 12 Jul 2022
Page range: 1333 - 1349

Abstract

Abstract

We determine the order of magnitude of the minimum clique cover of the edges of a binomial, r-uniform, random hypergraph G(r)(n, p), p fixed. In doing so, we combine the ideas from the proofs of the graph case (r = 2) in Frieze and Reed [Covering the edges of a random graph by cliques, Combinatorica 15 (1995) 489–497] and Guo, Patten, Warnke [Prague dimension of random graphs, manuscript submitted for publication].

Keywords

  • r-uniform random hypergraph
  • clique covering

MSC 2010

  • 05C65
  • 05C80
  • 05C62
  • 05C69
  • 05C70
  • 05C75
access type Open Access

On Singular Signed Graphs with Nullspace Spanned by a Full Vector: Signed Nut Graphs

Published Online: 12 Jul 2022
Page range: 1351 - 1382

Abstract

Abstract

A signed graph has edge weights drawn from the set {+1, −1}, and is sign-balanced if it is equivalent to an unsigned graph under the operation of sign switching; otherwise it is sign-unbalanced. A nut graph has a one dimensional kernel of the 0-1 adjacency matrix with a corresponding eigenvector that is full. In this paper we generalise the notion of nut graphs to signed graphs. Orders for which regular nut graphs with all edge weights +1 exist have been determined recently for the degrees up to 12. By extending the definition to signed graphs, we here find all pairs (ρ, n) for which a ρ-regular nut graph (sign-balanced or sign-unbalanced) of order n exists with ρ ≤ 11. We devise a construction for signed nut graphs based on a smaller ‘seed’ graph, giving infinite series of both sign-balanced and sign-unbalanced ρ -regular nut graphs. Orders for which a regular nut graph with ρ = n − 1 exists are characterised; they are sign-unbalanced with an underlying graph Kn for which n ≡ 1 (mod 4). Orders for which a regular sign-unbalanced nut graph with ρ = n − 2 exists are also characterised; they have an underlying cocktail-party graph CP(n) with even order n ≥ 8.

Keywords

  • signed graph
  • nut graph
  • singular graph
  • graph spectrum
  • Fowler construction
  • sign-balanced graph
  • sign-unbalanced graph
  • cocktail-party graph

MSC 2010

  • 05C50
  • 15A18
  • 05C22
  • 05C92
access type Open Access

A Note on Packing of Uniform Hypergraphs

Published Online: 12 Jul 2022
Page range: 1383 - 1388

Abstract

Abstract

We say that two n-vertex hypergraphs H1 and H2 pack if they can be found as edge-disjoint subhypergraphs of the complete hypergraph Kn. Whilst the problem of packing of graphs (i.e., 2-uniform hypergraphs) has been studied extensively since seventies, much less is known about packing of k-uniform hypergraphs for k ≥ 3. Naroski [Packing of nonuniform hypergraphs - product and sum of sizes conditions, Discuss. Math. Graph Theory 29 (2009) 651–656] defined the parameter mk(n) to be the smallest number m such that there exist two n-vertex k-uniform hypergraphs with total number of edges equal to m which do not pack, and conjectured that mk(n) = Θ (nk−1). In this note we show that this conjecture is far from being truth. Namely, we prove that the growth rate of mk(n) is of order nk/2 exactly for even k’s and asymptotically for odd k’s.

Keywords

  • packing
  • hypergraphs

MSC 2010

  • 05C35

Plan your remote conference with Sciendo