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

#### Search

- Open Access

Distance-Local Rainbow Connection Number

Page range: 1027 - 1039

#### Abstract

Under an edge coloring (not necessarily proper), a rainbow path is a path whose edge colors are all distinct. The _{d}_{d}_{d}_{d}

#### Keywords

- rainbow connection
- chromatic number
- line graph

#### MSC 2010

- 05C15
- 05C38
- 05C40

- Open Access

Flippable Edges in Triangulations on Surfaces

Page range: 1041 - 1059

#### Abstract

Concerning diagonal flips on triangulations, Gao

#### Keywords

- triangulation
- diagonal flip
- surface

#### MSC 2010

- 05C10

- Open Access

Singular Turán Numbers and Worm-Colorings

Page range: 1061 - 1074

#### Abstract

A subgraph _{S}_{S}_{3} and _{S}_{3}) for all _{S}_{r}_{+1}) for large enough

We also explore the connection to the so-called

#### Keywords

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

#### MSC 2010

- 05C35
- 05D10

#### Abstract

An edge coloring _{f}_{f}_{f}_{f}_{f}

#### Keywords

- edge coloring
- anti-Ramsey number
- dominating set

#### MSC 2010

- 05C15

- Open Access

Decomposing 10-Regular Graphs into Paths of Length 5

Page range: 1089 - 1097

#### Abstract

Let

#### Keywords

- 10-regular graph
- decomposition
- path

#### MSC 2010

- 05C38
- 05C70

- Open Access

(C _{3}, C _{4}, C _{5}, C _{7})-Free Almost Well-Dominated Graphs

_{3},

_{4},

_{5},

_{7})-Free Almost Well-Dominated Graphs

Page range: 1099 - 1117

#### Abstract

The _{3}, _{4}, _{5}, _{7})-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

#### Abstract

The Turán number of a graph _{ℓ}_{ℓ}_{ℓ}_{1}) for all positive integers _{2}) and characterized all extremal graphs for all positive integers _{3}) for all positive integers _{ℓ}_{ℓ}

#### Keywords

- Turán number
- disjoint copies
- ·

#### MSC 2010

- 05C35

- Open Access

Bounds on the Double Italian Domination Number of a Graph

Page range: 1129 - 1137

#### Abstract

For a graph _{v}_{∈}_{V} f_{{}_{R}_{3}}(

#### Keywords

- Italian domination
- double Italian domination
- probabilistic methods

#### MSC 2010

- 05C69

- Open Access

Finding Dominating Induced Matchings in P _{9}-Free Graphs in Polynomial Time

_{9}-Free Graphs in Polynomial Time

Page range: 1139 - 1162

#### Abstract

Let _{7}-free graphs and in polynomial time for _{8}-free graphs. In this paper, we solve it in polynomial time for _{9}-free graphs.

#### Keywords

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

#### MSC 2010

- 05C69
- 68R10

- Open Access

Cyclic Permutations in Determining Crossing Numbers

Page range: 1163 - 1183

#### Abstract

The crossing number of a graph ^{*}+ _{n}^{*} consisting of five vertices and of three edges incident with the same vertex is given. Up to now, the crossing numbers of _{n}^{*}+ _{n}^{*} + _{n}_{n}_{n}_{n}

#### Keywords

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

#### MSC 2010

- 05C10
- 05C38

- Open Access

More on the Rainbow Disconnection in Graphs

Page range: 1185 - 1204

#### Abstract

Let

#### 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

- Open Access

Antimagic Labeling of Some Biregular Bipartite Graphs

Page range: 1205 - 1218

#### Abstract

An antimagic labeling of a graph _{2} is antimagic. The conjecture remains open though it was verified for several classes of graphs such as regular graphs. A bipartite graph is called (^{2} +

#### Keywords

- antimagic labeling
- bipartite
- biregular

#### MSC 2010

- 05C69

- Open Access

On Small Balanceable, Strongly-Balanceable and Omnitonal Graphs

Page range: 1219 - 1235

#### Abstract

In Ramsey Theory for graphs we are given a graph _{0} such that, for any _{0}, any red/blue colouring of the edges of _{n}_{n}_{n}_{n}

These parameters were introduced by Caro, Hansberg and Montejano. These authors also introduce the more general omnitonal number ot(

In this paper we shall catalogue bal(

#### Keywords

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

#### MSC 2010

- 05C15
- 05C55

- Open Access

More Aspects of Arbitrarily Partitionable Graphs

Page range: 1237 - 1261

#### Abstract

A graph _{1}, . . ., n_{p}) partitioning _{1}, . . ., _{p}_{i}_{i}

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

#### 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

- Open Access

Nested Locally Hamiltonian Graphs and the Oberly-Sumner Conjecture

Page range: 1281 - 1312

#### Abstract

A graph ^{2}𝒫) if ^{m}C^{k}H^{0}^{0}_{1,3}-free graph that is locally connected is hamiltonian. They conjectured that for _{1,}_{k}_{+3}-free graph that is locally (_{1,}_{k}_{+3}-free graph that is locally _{1,}_{k}_{+4}-free locally

#### Keywords

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

#### MSC 2010

- 05C60

- Open Access

More on Signed Graphs with at Most Three Eigenvalues

Page range: 1313 - 1331

#### 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

- Open Access

Covering the Edges of a Random Hypergraph by Cliques

Page range: 1333 - 1349

#### Abstract

We determine the order of magnitude of the minimum clique cover of the edges of a binomial, ^{(}^{r}^{)}(

#### Keywords

- r-uniform random hypergraph
- clique covering

#### MSC 2010

- 05C65
- 05C80
- 05C62
- 05C69
- 05C70
- 05C75

- Open Access

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

Page range: 1351 - 1382

#### Abstract

A signed graph has edge weights drawn from the set {+1, −1}, and is _{n}

#### 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

- Open Access

A Note on Packing of Uniform Hypergraphs

Page range: 1383 - 1388

#### Abstract

We say that two _{1} and _{2} pack if they can be found as edge-disjoint subhypergraphs of the complete hypergraph _{n}_{k}_{k}^{k−1}). In this note we show that this conjecture is far from being truth. Namely, we prove that the growth rate of _{k}^{k/2} exactly for even

#### Keywords

- packing
- hypergraphs

#### MSC 2010

- 05C35