Graph Theory

This section of Discrete Mathematics & Theoretical Computer Science seeks high quality articles on structural and algorithmic aspects of graphs and related discrete mathematical models. We particularly seek topics with an intersection between discrete mathematics and computer science. We handle submissions in all areas of finite graph theory.


A sufficient condition for a balanced bipartite digraph to be hamiltonian

Wang, Ruixia.
We describe a new type of sufficient condition for a balanced bipartite digraph to be hamiltonian. Let $D$ be a balanced bipartite digraph and $x,y$ be distinct vertices in $D$. $\{x, y\}$ dominates a vertex $z$ if $x\rightarrow z$ and $y\rightarrow z$; in this case, we call the pair $\{x, y\}$ […]

Circular Separation Dimension of a Subclass of Planar Graphs

Bharathi, Arpitha P. ; De, Minati ; Lahiri, Abhiruk.
A pair of non-adjacent edges is said to be separated in a circular ordering of vertices, if the endpoints of the two edges do not alternate in the ordering. The circular separation dimension of a graph $G$, denoted by $\pi^\circ(G)$, is the minimum number of circular orderings of the vertices of $G$ […]

On path-cycle decompositions of triangle-free graphs

Jiménez, Andrea ; Wakabayashi, Yoshiko.
In this work, we study conditions for the existence of length-constrained path-cycle decompositions, that is, partitions of the edge set of a graph into paths and cycles of a given minimum length. Our main contribution is the characterization of the class of all triangle-free graphs with odd […]

Tight upper bound on the maximum anti-forcing numbers of graphs

Shi, Lingjuan ; Zhang, Heping.
Let $G$ be a simple graph with a perfect matching. Deng and Zhang showed that the maximum anti-forcing number of $G$ is no more than the cyclomatic number. In this paper, we get a novel upper bound on the maximum anti-forcing number of $G$ and investigate the extremal graphs. If $G$ has a perfect […]

On rank-width of even-hole-free graphs

Adler, Isolde ; Le, Ngoc Khang ; Müller, Haiko ; Radovanović, Marko ; Trotignon, Nicolas ; Vušković, Kristina.
We present a class of (diamond, even hole)-free graphs with no clique cutset that has unbounded rank-width. In general, even-hole-free graphs have unbounded rank-width, because chordal graphs are even-hole-free. A.A. da Silva, A. Silva and C. Linhares-Sales (2010) showed that planar even-hole-free […]

Irreversible 2-conversion set in graphs of bounded degree

Kynčl, Jan ; Lidický, Bernard ; Vyskočil, Tomáš.
An irreversible $k$-threshold process (also a $k$-neighbor bootstrap percolation) is a dynamic process on a graph where vertices change color from white to black if they have at least $k$ black neighbors. An irreversible $k$-conversion set of a graph $G$ is a subset $S$ of vertices of $G$ such […]

Characterizations of minimal dominating sets and the well-dominated property in lexicographic product graphs

Gözüpek, Didem ; Hujdurović, Ademir ; Milanič, Martin.
A graph is said to be well-dominated if all its minimal dominating sets are of the same size. The class of well-dominated graphs forms a subclass of the well studied class of well-covered graphs. While the recognition problem for the class of well-covered graphs is known to be co-NP-complete, the […]

On a combination of the 1-2-3 Conjecture and the Antimagic Labelling Conjecture

Bensmail, Julien ; Senhaji, Mohammed ; Szabo Lyngsie, Kasper.
This paper is dedicated to studying the following question: Is it always possible to injectively assign the weights 1, ..., |E(G)| to the edges of any given graph G (with no component isomorphic to K2) so that every two adjacent vertices of G get distinguished by their sums of incident weights? One […]

Nonrepetitive edge-colorings of trees

Kündgen, A. ; Talbot, T..
A repetition is a sequence of symbols in which the first half is the same as the second half. An edge-coloring of a graph is repetition-free or nonrepetitive if there is no path with a color pattern that is a repetition. The minimum number of colors so that a graph has a nonrepetitive […]

Equivalence of the filament and overlap graphs of subtrees of limited trees

Enright, Jessica ; Stewart, Lorna.
The overlap graphs of subtrees of a tree are equivalent to subtree filament graphs, the overlap graphs of subtrees of a star are cocomparability graphs, and the overlap graphs of subtrees of a caterpillar are interval filament graphs. In this paper, we show the equivalence of many more classes of […]

Graphs of Edge-Intersecting and Non-Splitting One Bend Paths in a Grid

Boyacı, Arman ; Ekim, Tınaz ; Shalom, Mordechai ; Zaks, Shmuel.
The families EPT (resp. EPG) Edge Intersection Graphs of Paths in a tree (resp. in a grid) are well studied graph classes. Recently we introduced the graph classes Edge-Intersecting and Non-Splitting Paths in a Tree ENPT, and in a Grid (ENPG). It was shown that ENPG contains an infinite hierarchy […]

The quotients between the (revised) Szeged index and Wiener index of graphs

Zhang, Huihui ; Chen, Jing ; Li, Shuchao.
Let $Sz(G),Sz^*(G)$ and $W(G)$ be the Szeged index, revised Szeged index and Wiener index of a graph $G.$ In this paper, the graphs with the fourth, fifth, sixth and seventh largest Wiener indices among all unicyclic graphs of order $n\geqslant 10$ are characterized; as well the graphs with the […]

The Existence of Planar Hypotraceable Oriented Graphs

van Aardt, Susan,  ; Burger, Alewyn Petrus ; Frick, Marietjie.
A digraph is \emph{traceable} if it has a path that visits every vertex. A digraph $D$ is \emph{hypotraceable} if $D$ is not traceable but $D-v$ is traceable for every vertex $v\in V(D)$. It is known that there exists a planar hypotraceable digraph of order $n$ for every $n\geq 7$, but no examples […]

A characterization of trees with equal 2-domination and 2-independence numbers

Brause, Christoph ; Henning, Michael A. ; Krzywkowski, Marcin.
A set $S$ of vertices in a graph $G$ is a $2$-dominating set if every vertex of $G$ not in $S$ is adjacent to at least two vertices in $S$, and $S$ is a $2$-independent set if every vertex in $S$ is adjacent to at most one vertex of $S$. The $2$-domination number $\gamma_2(G)$ is the minimum […]

A New Game Invariant of Graphs: the Game Distinguishing Number

Gravier, Sylvain ; Meslem, Kahina ; Schmidt, Simon ; Slimani, Souad.
The distinguishing number of a graph $G$ is a symmetry related graph invariant whose study started two decades ago. The distinguishing number $D(G)$ is the least integer $d$ such that $G$ has a $d$-distinguishing coloring. A distinguishing $d$-coloring is a coloring […]

Mixing Times of Markov Chains on Degree Constrained Orientations of Planar Graphs

Felsner, Stefan ; Heldt, Daniel.
We study Markov chains for $\alpha$-orientations of plane graphs, these are orientations where the outdegree of each vertex is prescribed by the value of a given function $\alpha$. The set of $\alpha$-orientations of a plane graph has a natural distributive lattice structure. The moves of the […]

Linear recognition of generalized Fibonacci cubes $Q_h(111)$

Rho, Yoomi ; Vesel, Aleksander.
The generalized Fibonacci cube $Q_h(f)$ is the graph obtained from the $h$-cube $Q_h$ by removing all vertices that contain a given binary string $f$ as a substring. In particular, the vertex set of the 3rd order generalized Fibonacci cube $Q_h(111)$ is the set of all binary strings $b_1b_2 \ldots […]

Matchings of quadratic size extend to long cycles in hypercubes

Dvořák, Tomáš.
Ruskey and Savage in 1993 asked whether every matching in a hypercube can be extended to a Hamiltonian cycle. A positive answer is known for perfect matchings, but the general case has been resolved only for matchings of linear size. In this paper we show that there is a quadratic function $q(n)$ […]

Connected Tropical Subgraphs in Vertex-Colored Graphs

Anglès d'Auriac, Jean-Alexandre ; Cohen, Nathann ; El Mafthoui, Hakim ; Harutyunyan, Ararat ; Legay, Sylvain ; Manoussakis, Yannis.
A subgraph of a vertex-colored graph is said to be tropical whenever it contains each color of the graph. In this work we study the problem of finding a minimal connected tropical subgraph. We first show that this problem is NP-Hard for trees, interval graphs and split graphs, but polynomial when […]

An extremal problem for a graphic sequence to have a realization containing every 2-tree with prescribed size

Zeng, De-Yan ; Yin, Jian-Hua.
A graph $G$ is a $2$-tree if $G=K_3$, or $G$ has a vertex $v$ of degree 2, whose neighbors are adjacent, and $G-v$ is a 2-tree. Clearly, if $G$ is a 2-tree on $n$ vertices, then $|E(G)|=2n-3$. A non-increasing sequence $\pi =(d_1, \ldots ,d_n)$ of nonnegative integers is a graphic […]

On degree-sequence characterization and the extremal number of edges for various Hamiltonian properties under fault tolerance

Chen, Shih-Yan ; Kao, Shin-Shin ; Su, Hsun.
Assume that $n, \delta ,k$ are integers with $0 \leq k < \delta < n$. Given a graph $G=(V,E)$ with $|V|=n$. The symbol $G-F, F \subseteq V$, denotes the graph with $V(G-F)=V-F$, and $E(G-F)$ obtained by $E$ after deleting the edges with at least one endvertex in $F$. $G$ is called $k$-vertex […]

Edge Disjoint Hamilton Cycles in Knödel Graphs

Paulraja, Palanivel Subramania Nadar ; Sampath Kumar, S.
The vertices of the Knödel graph $W_{\Delta, n}$ on $n \geq 2$ vertices, $n$ even, and of maximum degree $\Delta, 1 \leq \Delta \leq \lfloor log_2(n) \rfloor$, are the pairs $(i,j)$ with $i=1,2$ and $0 \leq j \leq \frac{n}{2} -1$. For $0 \leq j \leq \frac{n}{2} -1$, there is an edge between vertex […]

Traceability of locally hamiltonian and locally traceable graphs

De Wet, Johan ; Van Aardt, Susan.
If $\mathcal{P}$ is a given graph property, we say that a graph $G$ is locally $\mathcal{P}$ if $\langle N(v) \rangle$ has property $\mathcal{P}$ for every $v \in V(G)$ where $\langle N(v) \rangle$ is the induced graph on the open neighbourhood of the vertex $v$. Pareek and Skupien (C. M. […]

The inapproximability for the $(0,1)$-additive number

Ahadi, Arash ; Dehghan, Ali.
An additive labeling of a graph $G$ is a function $\ell :V(G) \rightarrow \mathbb{N}$, such that for every two adjacent vertices $v$ and $u$ of $G$, $\Sigma_{w \sim v} \ell (w) \neq \Sigma_{w \sim u} \ell (w)$ ($x \sim y$ means that $x$ is joined to $y$). The additive number of $G$, denoted […]

The irregularity of two types of trees

Jianxi, Li ; Liu, Yang ; Shiu, Wai.
The irregularity of a graph $G$ is defined as the sum of weights $|d(u)-d(v)|$ of all edges $uv$ of $G$, where $d(u)$ and $d(v)$ are the degrees of the vertices $u$ and $v$ in $G$, respectively. In this paper, some structural properties on trees with maximum (or minimum) irregularity among trees […]

Partitioning the vertex set of $G$ to make $G\,\Box\, H$ an efficient open domination graph

Šumenjak, Tadeja Kraner ; Peterin, Iztok ; Rall, Douglas F. ; Tepeh, Aleksandra.
A graph is an efficient open domination graph if there exists a subset of vertices whose open neighborhoods partition its vertex set. We characterize those graphs $G$ for which the Cartesian product $G \Box H$ is an efficient open domination graph when $H$ is a complete graph of order at least 3 or […]

Planar graphs with $\Delta \geq 7$ and no triangle adjacent to a $C_4$ are minimally edge and total choosable

Bonamy, Marthe ; Lévêque, Benjamin ; Pinlou, Alexandre.
For planar graphs, we consider the problems of list edge coloring and list total coloring. Edge coloring is the problem of coloring the edges while ensuring that two edges that are adjacent receive different colors. Total coloring is the problem of coloring the edges and the vertices […]

Rainbow eulerian multidigraphs and the product of cycles

López, Susana ; Muntaner-Batle, Francesc-Antoni.
An arc colored eulerian multidigraph with $l$ colors is rainbow eulerian if there is an eulerian circuit in which a sequence of $l$ colors repeats. The digraph product that refers the title was introduced by Figueroa-Centeno et al. as follows: let $D$ be a digraph and let $\Gamma$ be a family of […]

Heredity for generalized power domination

Dorbec, Paul ; Varghese, Seethu ; Vijayakumar, Ambat.
In this paper, we study the behaviour of the generalized power domination number of a graph by small changes on the graph, namely edge and vertex deletion and edge contraction. We prove optimal bounds for $\gamma_{p,k}(G-e)$, $\gamma_{p,k}(G/e)$ and for $\gamma_{p,k}(G-v)$ in terms of […]

Open k-monopolies in graphs: complexity and related concepts

Kuziak, Dorota ; Peterin, Iztok ; Yero, Ismael G..
Closed monopolies in graphs have a quite long range of applications in several problems related to overcoming failures, since they frequently have some common approaches around the notion of majorities, for instance to consensus problems, diagnosis problems or voting systems. We introduce here open […]

Edge-partitioning graphs into regular and locally irregular components

Bensmail, Julien ; Stevens, Brett.
A graph is locally irregular if every two adjacent vertices have distinct degrees. Recently, Baudon et al. introduced the notion of decomposition into locally irregular subgraphs. They conjectured that for almost every graph $G$, there exists a minimum integer $\chi^{\prime}_{\mathrm{irr}}(G)$ such […]

The complexity of deciding whether a graph admits an orientation with fixed weak diameter

Bensmail, Julien ; Duvignau, Romaric ; Kirgizov, Sergey.
An oriented graph $\overrightarrow{G}$ is said weak (resp. strong) if, for every pair $\{ u,v \}$ of vertices of $\overrightarrow{G}$, there are directed paths joining $u$ and $v$ in either direction (resp. both directions). In case, for every pair of vertices, some of these directed paths have […]

Vertex-Coloring Edge-Weighting of Bipartite Graphs with Two Edge Weights

Lu, Hongliang.
Let $G$ be a graph and $\mathcal{S}$ be a subset of $Z$. A vertex-coloring $\mathcal{S}$-edge-weighting of $G$ is an assignment of weights by the elements of $\mathcal{S}$ to each edge of $G$ so that adjacent vertices have different sums of incident edges weights. It was proved that every […]

The double competition multigraph of a digraph

Sano, Yoshio ; Park, Jeongmi.
In this article, we introduce the notion of the double competition multigraph of a digraph. We give characterizations of the double competition multigraphs of arbitrary digraphs, loopless digraphs, reflexive digraphs, and acyclic digraphs in terms of edge clique partitions of the multigraphs.

The game colouring number of powers of forests

Andres, Stephan Dominique ; Hochstättler, Winfried.
We prove that the game colouring number of the $m$-th power of a forest of maximum degree $\Delta\ge3$ is bounded from above by \[\frac{(\Delta-1)^m-1}{\Delta-2}+2^m+1,\] which improves the best known bound by an asymptotic factor of 2.

Cubical coloring — fractional covering by cuts and semidefinite programming

Šámal, Robert.
We introduce a new graph parameter that measures fractional covering of a graph by cuts. Besides being interesting in its own right, it is useful for study of homomorphisms and tension-continuous mappings. We study the relations with chromatic number, bipartite density, and other graph parameters. […]

Disimplicial arcs, transitive vertices, and disimplicial eliminations

Eguia, Martiniano ; Soulignac, Francisco, .
In this article we deal with the problems of finding the disimplicial arcs of a digraph and recognizing some interesting graph classes defined by their existence. A diclique of a digraph is a pair $V$ → $W$ of sets of vertices such that $v$ → $w$ is an arc for every $v$ ∈ $V$ […]

Packing Plane Perfect Matchings into a Point Set

Biniaz, Ahmad ; Bose, Prosenjit ; Maheshwari, Anil ; Smid, Michiel.
Given a set $P$ of $n$ points in the plane, where $n$ is even, we consider the following question: How many plane perfect matchings can be packed into $P$? For points in general position we prove the lower bound of ⌊log2$n$⌋$-1$. For some special configurations of point […]

The complexity of $P$4-decomposition of regular graphs and multigraphs

Diwan, Ajit ; Dion, Justine ; Mendell, David ; Plantholt, Michael ; Tipnis, Shailesh.
Let G denote a multigraph with edge set E(G), let µ(G) denote the maximum edge multiplicity in G, and let Pk denote the path on k vertices. Heinrich et al.(1999) showed that P4 decomposes a connected 4-regular graph G if and only if |E(G)| is divisible by 3. We show that P4 decomposes a […]

On graphs double-critical with respect to the colouring number

Kriesell, Matthias ; Pedersen, Anders.
The colouring number col($G$) of a graph $G$ is the smallest integer $k$ for which there is an ordering of the vertices of $G$ such that when removing the vertices of $G$ in the specified order no vertex of degree more than $k-1$ in the remaining graph is removed at any step. An edge $e$ of a graph […]

The game chromatic number of trees and forests

Dunn, Charles ; Larsen, Victor ; Lindke, Kira ; Retter, Troy ; Toci, Dustin.
While the game chromatic number of a forest is known to be at most 4, no simple criteria are known for determining the game chromatic number of a forest. We first state necessary and sufficient conditions for forests with game chromatic number 2 and then investigate the differences between forests […]

Snarks with total chromatic number 5

Brinkmann, Gunnar ; Preissmann, Myriam ; Sasaki, Diana.
A k-total-coloring of G is an assignment of k colors to the edges and vertices of G, so that adjacent and incident elements have different colors. The total chromatic number of G, denoted by χT(G), is the least k for which G has a k-total-coloring. It was proved by Rosenfeld that the total chromatic […]

Maximum difference about the size of optimal identifying codes in graphs differing by one vertex

Pelto, Mikko.
Let G=(V,E) be a simple undirected graph. We call any subset C⊆V an identifying code if the sets I(v)={c∈C | {v,c}∈E or v=c } are distinct and non-empty for all vertices v∈V. A graph is called twin-free if there is an identifying code in the graph. The identifying code with minimum size in a […]

Graphs with large disjunctive total domination number

Henning, Michael A. ; Naicker, Viroshan.
Let G be a graph with no isolated vertex. In this paper, we study a parameter that is a relaxation of arguably the most important domination parameter, namely the total domination number, γt(G). A set S of vertices in G is a disjunctive total dominating set of G if every vertex is adjacent to a […]

Extending a perfect matching to a Hamiltonian cycle

Alahmadi, Adel ; Aldred, Robert E. L. ; Alkenani, Ahmad ; Hijazi, Rola ; Solé, P. ; Thomassen, Carsten.
Ruskey and Savage conjectured that in the d-dimensional hypercube, every matching M can be extended to a Hamiltonian cycle. Fink verified this for every perfect matching M, remarkably even if M contains external edges. We prove that this property also holds for sparse spanning regular subgraphs of […]

A conjecture on the number of Hamiltonian cycles on thin grid cylinder graphs

Bodroža-Pantić, Olga ; Kwong, Harris ; Pantić, Milan.
We study the enumeration of Hamiltonian cycles on the thin grid cylinder graph $C_m \times P_{n+1}$. We distinguish two types of Hamiltonian cycles, and denote their numbers $h_m^A(n)$ and $h_m^B(n)$. For fixed $m$, both of them satisfy linear homogeneous recurrence relations with constant […]

On probe 2-clique graphs and probe diamond-free graphs

Bonomo, Flavia ; Figueiredo, Celina M. H.,  ; Duran, Guillermo ; Grippo, Luciano N. ; Safe, Martín D. ; Szwarcfiter, Jayme L..
Given a class G of graphs, probe G graphs are defined as follows. A graph G is probe G if there exists a partition of its vertices into a set of probe vertices and a stable set of nonprobe vertices in such a way that non-edges of G, whose endpoints are nonprobe vertices, can be added so that the […]

p-box: a new graph model

Soto, Mauricio ; Thraves-Caro, Christopher.
In this document, we study the scope of the following graph model: each vertex is assigned to a box in ℝd and to a representative element that belongs to that box. Two vertices are connected by an edge if and only if its respective boxes contain the opposite representative element. We focus our […]

Guarded subgraphs and the domination game

Brešar, Boštjan ; Klavžar, Sandi ; Košmrlj, Gasper ; Rall, Doug F..
We introduce the concept of guarded subgraph of a graph, which as a condition lies between convex and 2-isometric subgraphs and is not comparable to isometric subgraphs. Some basic metric properties of guarded subgraphs are obtained, and then this concept is applied to the domination game. In this […]

Edge stability in secure graph domination

Burger, Anton Pierre ; Villiers, Alewyn Petrus,  ; Vuuren, Jan Harm, .
A subset X of the vertex set of a graph G is a secure dominating set of G if X is a dominating set of G and if, for each vertex u not in X, there is a neighbouring vertex v of u in X such that the swap set (X-v)∪u is again a dominating set of G. The secure domination number of G is the cardinality […]

Connectivity of Fibonacci cubes, Lucas cubes and generalized cubes

Azarija, Jernej ; Klavžar, Sandi ; Lee, Jaehun ; Rho, Yoomi.
If f is a binary word and d a positive integer, then the generalized Fibonacci cube Qd(f) is the graph obtained from the d-cube Qd by removing all the vertices that contain f as a factor, while the generalized Lucas cube Qd(lucas(f)) is the graph obtained from Qd by removing all the vertices that […]

Symmetric bipartite graphs and graphs with loops

Cairns, Grant ; Mendan, Stacey.
We show that if the two parts of a finite bipartite graph have the same degree sequence, then there is a bipartite graph, with the same degree sequences, which is symmetric, in that it has an involutive graph automorphism that interchanges its two parts. To prove this, we study the relationship […]

On the 1-2-3-conjecture

Davoodi, Akbar ; Omoomi, Behnaz.
A k-edge-weighting of a graph G is a function w:E(G)→{1,…,k}. An edge-weighting naturally induces a vertex coloring c, where for every vertex v∈V(G), c(v)=∑e∼vw(e). If the induced coloring c is a proper vertex coloring, then w is called a vertex-coloring k-edge-weighting (VC k-EW). Karoński et al. […]

An approximability-related parameter on graphs―-properties and applications

Engström, Robert ; Färnqvist, Tommy ; Jonsson, Peter ; Thapper, Johan.
We introduce a binary parameter on optimisation problems called separation. The parameter is used to relate the approximation ratios of different optimisation problems; in other words, we can convert approximability (and non-approximability) result for one problem into (non)-approximability results […]

Ore-degree threshold for the square of a Hamiltonian cycle

DeBiasio, Louis ; Faizullah, Safi ; Khan, Imdadullah.
A classic theorem of Dirac from 1952 states that every graph with minimum degree at least n=2 contains a Hamiltonian cycle. In 1963, P´osa conjectured that every graph with minimum degree at least 2n=3 contains the square of a Hamiltonian cycle. In 1960, Ore relaxed the degree condition in the […]

Generalized dynamic storage allocation

Kierstead, H. A. ; Saoub, Karin R..
Dynamic Storage Allocation is a problem concerned with storing items that each have weight and time restrictions. Approximate algorithms have been constructed through online coloring of interval graphs. We present a generalization that uses online coloring of tolerance graphs. We utilize […]

Toppling numbers of complete and random graphs

Bonato, Anthony ; Kinnersley, William B. ; Pralat, Pawel.
We study a two-person game played on graphs based on the widely studied chip-firing game. Players Max and Min alternately place chips on the vertices of a graph. When a vertex accumulates as many chips as its degree, it fires, sending one chip to each neighbour; this may in turn cause other vertices […]

Partitioning the vertex set of a bipartite graph into complete bipartite subgraphs

Duginov, Oleg.
Given a graph and a positive integer k, the biclique vertex-partition problem asks whether the vertex set of the graph can be partitioned into at most k bicliques (connected complete bipartite subgraphs). It is known that this problem is NP-complete for bipartite graphs. In this paper we investigate […]

Packing and covering the balanced complete bipartite multigraph with cycles and stars

Lee, Hung-Chih.
Let Ck denote a cycle of length k and let Sk denote a star with k edges. For multigraphs F, G and H, an (F,G)-decomposition of H is an edge decomposition of H into copies of F and G using at least one of each. For L⊆H and R⊆rH, an (F,G)-packing (resp. (F,G)-covering) of H with leave L (resp. padding […]

Bounding the monomial index and (1,l)-weight choosability of a graph

Seamone, Ben.
Let G = (V,E) be a graph. For each e ∈E(G) and v ∈V(G), let Le and Lv, respectively, be a list of real numbers. Let w be a function on V(G) ∪E(G) such that w(e) ∈Le for each e ∈E(G) and w(v) ∈Lv for each v ∈V(G), and let cw be the vertex colouring obtained by cw(v) = w(v) + ∑ₑ ∋vw(e). A graph is […]

Genus distributions of cubic series-parallel graphs

Gross, Jonathan L. ; Kotrbčík, Michal ; Sun, Timothy.
We derive a quadratic-time algorithm for the genus distribution of any 3-regular, biconnected series-parallel graph, which we extend to any biconnected series-parallel graph of maximum degree at most 3. Since the biconnected components of every graph of treewidth 2 are series-parallel graphs, this […]

Complexity of conditional colouring with given template

Dukes, Peter J. ; Lowdon, Steve ; Macgillivray, Gary.
We study partitions of the vertex set of a given graph into cells that each induce a subgraph in a given family, and for which edges can have ends in different cells only when those cells correspond to adjacent vertices of a fixed template graph H. For triangle-free templates, a general collection […]

Oriented diameter and rainbow connection number of a graph

Huang, Xiaolong ; Li, Hengzhe ; Li, Xueliang ; Sun, Yuefang.
The oriented diameter of a bridgeless graph G is min diam(H) | H is a strang orientation of G. A path in an edge-colored graph G, where adjacent edges may have the same color, is called rainbow if no two edges of the path are colored the same. The rainbow connection number rc(G) of G is the smallest […]

A four-sweep LBFS recognition algorithm for interval graphs

Li, Peng ; Wu, Yaokun.
In their 2009 paper, Corneil et al. design a linear time interval graph recognition algorithm based on six sweeps of Lexicographic Breadth-First Search (LBFS) and prove its correctness. They believe that their corresponding 5-sweep LBFS interval graph recognition algorithm is also correct. Thanks to […]

Balancedness of subclasses of circular-arc graphs

Bonomo, Flavia ; Duran, Guillermo ; Safe, Martın D. ; Wagler, Annegret K..
A graph is balanced if its clique-vertex incidence matrix contains no square submatrix of odd order with exactly two ones per row and per column. There is a characterization of balanced graphs by forbidden induced subgraphs, but no characterization by mininal forbidden induced subgraphs is known, […]

The generalized 3-connectivity of Lexicographic product graphs

Li, Xueliang ; Mao, Yaping.
The generalized k-connectivity κk(G) of a graph G, first introduced by Hager, is a natural generalization of the concept of (vertex-)connectivity. Denote by G^H and G&Box;H the lexicographic product and Cartesian product of two graphs G and H, respectively. In this paper, we prove that for any two […]

A variant of Niessen’s problem on degreesequences of graphs

Guo, Jiyun ; Yin, Jianhua.
Let (a1,a2,\textellipsis,an) and (b1,b2,\textellipsis,bn) be two sequences of nonnegative integers satisfying the condition that b1>=b2>=...>=bn, ai<= bi for i=1,2,\textellipsis,n and ai+bi>=ai+1+bi+1 for i=1,2,\textellipsis, n-1. In this paper, we give two different conditions, one of which is […]

On the Meyniel condition for hamiltonicity in bipartite digraphs

Adamus, Janusz ; Adamus, Lech ; Yeo, Anders.
We prove a sharp Meyniel-type criterion for hamiltonicity of a balanced bipartite digraph: For a≥2, a strongly connected balanced bipartite digraph D on 2a vertices is hamiltonian if d(u)+d(v)≥3a whenever uv∉A(D) and vu∉A(D). As a consequence, we obtain a sharp sufficient condition for […]

On the Cartesian product of of an arbitrarily partitionable graph and a traceable graph

Baudon, Olivier ; Bensmail, Julien ; Kalinowski, Rafał ; Marczyk, Antoni ; Przybyło, Jakub ; Wozniak, Mariusz.
A graph G of order n is called arbitrarily partitionable (AP, for short) if, for every sequence τ=(n1,\textellipsis,nk) of positive integers that sum up to n, there exists a partition (V1,\textellipsis,Vk) of the vertex set V(G) such that each set Vi induces a connected subgraph of order ni. A graph […]

The Price of Connectivity for Vertex Cover

Camby, Eglantine ; Cardinal, Jean ; Fiorini, Samuel ; Schaudt, Oliver.
The vertex cover number of a graph is the minimum number of vertices that are needed to cover all edges. When those vertices are further required to induce a connected subgraph, the corresponding number is called the connected vertex cover number, and is always greater or equal to the vertex cover […]

The total irregularity of a graph

Abdo, Hosam ; Brandt, Stephan ; Dimitrov, D..
In this note a new measure of irregularity of a graph G is introduced. It is named the total irregularity of a graph and is defined as irr(t)(G) - 1/2 Sigma(u, v is an element of V(G)) vertical bar d(G)(u) - d(G)(v)vertical bar, where d(G)(u) denotes the degree of a vertex u is an element of V(G). […]

Strong parity vertex coloring of plane graphs

Kaiser, Tomas ; Rucky, Ondrej ; Stehlik, Matej ; Škrekovski, Riste.
A strong parity vertex coloring of a 2-connected plane graph is a coloring of the vertices such that every face is incident with zero or an odd number of vertices of each color. We prove that every 2-connected loopless plane graph has a strong parity vertex coloring with 97 colors. Moreover the […]

List circular backbone colouring

Havet, Frédéric ; King, Andrew.
A natural generalization of graph colouring involves taking colours from a metric space and insisting that the endpoints of an edge receive colours separated by a minimum distance dictated by properties of the edge. In the q-backbone colouring problem, these minimum distances are either q or 1, […]

Efficient open domination in graph products

Kuziak, Dorota ; Peterin, Iztok ; Yero, Ismael Gonzalez.
A graph G is an efficient open domination graph if there exists a subset D of V(G) for which the open neighborhoods centered in vertices of D form a partition of V(G). We completely describe efficient open domination graphs among lexicographic, strong, and disjunctive products of graphs. For the […]

On Hamiltonian Paths and Cycles in Sufficiently Large Distance Graphs

Löwenstein, Christian ; Rautenbach, Dieter ; Soták, Roman.
For a positive integer n∈ℕ and a set D⊆ ℕ, the distance graph GnD has vertex set { 0,1,\textellipsis,n-1} and two vertices i and j of GnD are adjacent exactly if |j-i|∈D. The condition gcd(D)=1 is necessary for a distance graph GnD being connected. Let D={d1,d2}⊆ℕ be such […]

On size, radius and minimum degree

Mukwembi, Simon.
Let G be a finite connected graph. We give an asymptotically tight upper bound on the size of G in terms of order, radius and minimum degree. Our result is a strengthening of an old classical theorem of Vizing (1967) if minimum degree is prescribed.

The resolving number of a graph Delia

Garijo, Delia ; González, Antonio ; Márquez, Alberto.
We study a graph parameter related to resolving sets and metric dimension, namely the resolving number, introduced by Chartrand, Poisson and Zhang. First, we establish an important difference between the two parameters: while computing the metric dimension of an arbitrary graph is known to be […]

1-local 33/24-competitive Algorithm for Multicoloring Hexagonal Graphs

Witkowski, Rafal ; Žerovnik, Janez.
In the frequency allocation problem, we are given a cellular telephone network whose geographical coverage area is divided into cells, where phone calls are serviced by assigned frequencies, so that none of the pairs of calls emanating from the same or neighboring cells is assigned the same […]

A new characterization and a recognition algorithm of Lucas cubes

Taranenko, Andrej.
Fibonacci and Lucas cubes are induced subgraphs of hypercubes obtained by excluding certain binary strings from the vertex set. They appear as models for interconnection networks, as well as in chemistry. We derive a characterization of Lucas cubes that is based on a peripheral expansion of a unique […]

Clique cycle transversals in graphs with few P₄'s

Bravo, Raquel ; Klein, Sulamita ; Nogueira, Loana Tito ; Protti, Fábio.
A graph is extended P4-laden if each of its induced subgraphs with at most six vertices that contains more than two induced P4's is 2K2,C4-free. A cycle transversal (or feedback vertex set) of a graph G is a subset T ⊆ V (G) such that T ∩ V (C) 6= ∅ for every cycle C of G; if, in addition, T is a […]

Maximal independent sets in bipartite graphs with at least one cycle

Li, Shuchao ; Zhang, Huihui ; Zhang, Xiaoyan.
A maximal independent set is an independent set that is not a proper subset of any other independent set. Liu [J.Q. Liu, Maximal independent sets of bipartite graphs, J. Graph Theory, 17 (4) (1993) 495-507] determined the largest number of maximal independent sets among all n-vertex bipartite […]

A note on the NP-hardness of two matching problems in induced subgrids

Demange, Marc ; Ekim, Tınaz.
Given a graph, finding the maximal matching of minimum size (MMM) and the induced matching of maximum size (MIM) have been very popular research topics during the last decades. In this paper, we give new complexity results, namely the NP-hardness of MMM and MIM in induced subgrids and we point out […]

Probe interval graphs and probe unit interval graphs on superclasses of cographs

Bonomo, Flavia ; Durán, Guillermo ; Grippo, Luciano N. ; Safe, Martın D..
A graph is probe (unit) interval if its vertices can be partitioned into two sets: a set of probe vertices and a set of nonprobe vertices, so that the set of nonprobe vertices is a stable set and it is possible to obtain a (unit) interval graph by adding edges with both endpoints in the set of […]

Removable edges in near-bricks

Wang, Xiumei ; He, Cheng ; Lin, Yixun.
For a brick apart from a few small graphs, Lovász (1987) proposed a conjecture on the existence of an edge whose deletion results in a graph with only one brick in its tight cut decomposition. Carvalho, Lucchesi, and Murty (2002) confirmed this conjecture by showing the existence of such two edges. […]

Improved bounds on the crossing number of butterfly network

Manuel, Paul D. ; Rajan, Bharati ; Rajasingh, Indra ; Beulah, P. Vasanthi.
We draw the r-dimensional butterfly network with 1 / 44r+O(r2r) crossings which improves the previous estimate given by Cimikowski (1996). We also give a lower bound which matches the upper bound obtained in this paper.

Bipartite powers of k-chordal graphs

Chandran, Sunil,  ; Mathew, Rogers.
Let k be an integer and k ≥3. A graph G is k-chordal if G does not have an induced cycle of length greater than k. From the definition it is clear that 3-chordal graphs are precisely the class of chordal graphs. Duchet proved that, for every positive integer m, if Gm is chordal then so is Gm+2. […]

The b-chromatic number of powers of cycles

Kohl, Anja.
A b-coloring of a graph G by k colors is a proper vertex coloring such that each color class contains a color-dominating vertex, that is, a vertex having neighbors in all other k-1 color classes. The b-chromatic number χb(G) is the maximum integer k for which G has a b-coloring by k colors. Let Cnr […]

All totally symmetric colored graphs

Grech, Mariusz ; Kisielewicz, Andrzej.
In this paper we describe all edge-colored graphs that are fully symmetric with respect to colors and transitive on every set of edges of the same color. They correspond to fully symmetric homogeneous factorizations of complete graphs. Our description completes the work done in our previous paper, […]

A chip-firing variation and a new proof of Cayley's formula

Kayll, Peter Mark ; Perkins, Dave.
We introduce a variation of chip-firing games on connected graphs. These 'burn-off' games incorporate the loss of energy that may occur in the physical processes that classical chip-firing games have been used to model. For a graph G=(V,E), a configuration of 'chips' on its nodes is a mapping C:V→ℕ. […]

Krausz dimension and its generalizations in special graph classes

Glebova, Olga ; Metelsky, Yury ; Skums, Pavel.
A Krausz (k,m)-partition of a graph G is a decomposition of G into cliques, such that any vertex belongs to at most k cliques and any two cliques have at most m vertices in common. The m-Krausz dimension kdimm(G) of the graph G is the minimum number k such that G has a Krausz (k,m)-partition. In […]

Further results on maximal nontraceable graphs of smallest size

Burger, Alewyn Petrus ; Singleton, Joy Elizabeth.
Let g(n) denote the minimum number of edges of a maximal nontraceable (MNT) graph of order n. In 2005 Frick and Singleton (Lower bound for the size of maximal nontraceable graphs, Electronic Journal of Combinatorics, 12(1) R32, 2005) proved that g(n) = ⌈3n-22 ⌉ for n ≥54 as well as for n ∈I, where […]

The determining number of Kneser graphs

Cáceres, José ; Garijo, Delia ; González, Antonio ; Márquez, Alberto ; Puertas, Marıa Luz.
A set of vertices S is a determining set of a graph G if every automorphism of G is uniquely determined by its action on S. The determining number of G is the minimum cardinality of a determining set of G. This paper studies the determining number of Kneser graphs. First, we compute the determining […]

Sequence variations of the 1-2-3 conjecture and irregularity strength

Seamone, Ben ; Stevens, Brett.
Karonski, Luczak, and Thomason (2004) conjecture that, for any connected graph G on at least three vertices, there exists an edge weighting from 1, 2, 3 such that adjacent vertices receive different sums of incident edge weights. Bartnicki, Grytczuk, and Niwcyk (2009) make a stronger conjecture, […]

Upper k-tuple domination in graphs

Chang, Gerard Jennhwa ; Dorbec, Paul ; Kim, Hye Kyung ; Raspaud, André ; Wang, Haichao ; Zhao, Weiliang.
For a positive integer k, a k-tuple dominating set of a graph G is a subset S of V (G) such that |N [v] ∩ S| ≥ k for every vertex v, where N [v] = {v} ∪ {u ∈ V (G) : uv ∈ E(G)}. The upper k-tuple domination number of G, denoted by Γ×k (G), is the maximum cardinality of a minimal k-tuple dominating […]

Secure frameproof codes through biclique covers

Hajiabolhassan, Hossein ; Moazami, Farokhlagha.
For a binary code Γ of length v, a v-word w produces by a set of codewords {w1,...,wr}⊆Γ if for all i=1,...,v, we have wi∈{w1i,...,wri} . We call a code r-secure frameproof of size t if |Γ|=t and for any v-word that is produced by two sets C1 and C2 of size at most r then the intersection of these […]

A note on planar Ramsey numbers for a triangle versus wheels

Zhou, Guofei ; Chen, Yaojun ; Miao, Zhengke ; Pirzada, Shariefuddin.
For two given graphs G and H , the planar Ramsey number P R ( G; H ) is the smallest integer n such that every planar graph F on n vertices either contains a copy of G , or its complement contains a copy of H . In this paper, we determine all planar Ramsey numbers for a triangle versus wheels.

On 4-valent Frobenius circulant graphs

Zhou, Sanming.
A 4-valent first-kind Frobenius circulant graph is a connected Cayley graph DLn(1, h) = Cay(Zn, H) on the additive group of integers modulo n, where each prime factor of n is congruent to 1 modulo 4 and H = {[1], [h], −[1], −[h]} with h a solution to the congruence equation x 2 + 1 ≡ 0 (mod n). In […]

Immersion containment and connectivity in color-critical graphs

Abu-Khzam, Faisal N. ; Langston, Michael A..
The relationship between graph coloring and the immersion order is considered. Vertex connectivity, edge connectivity and related issues are explored. It is shown that a t-chromatic graph G contains either an immersed Kt or an immersed t-chromatic subgraph that is both 4-vertex-connected and […]

Acyclic chromatic index of fully subdivided graphs and Halin graphs

Basavaraju, Manu.
An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a'(G). A graph G is called fully subdivided if it is […]

Random Cayley digraphs of diameter 2 and given degree

Lladser, Manuel E. ; Potočnik, Primož ; Širáň, Jozef ; Wilson, Mark C..
We consider random Cayley digraphs of order n with uniformly distributed generating sets of size k. Specifically, we are interested in the asymptotics of the probability that such a Cayley digraph has diameter two as n -> infinity and k = f(n), focusing on the functions f(n) = left […]

Graphs with many vertex-disjoint cycles

Rautenbach, Dieter ; Regen, Friedrich.
We study graphs G in which the maximum number of vertex-disjoint cycles nu(G) is close to the cyclomatic number mu(G), which is a natural upper bound for nu(G). Our main result is the existence of a finite set P(k) of graphs for all k is an element of N-0 such that every 2-connected graph G with […]

On paths, trails and closed trails in edge-colored graphs

Gourvès, Laurent ; Lyra, Adria ; Martinhon, Carlos A. ; Monnot, Jérôme.
In this paper we deal from an algorithmic perspective with different questions regarding properly edge-colored (or PEC) paths, trails and closed trails. Given a c-edge-colored graph G(c), we show how to polynomially determine, if any, a PEC closed trail subgraph whose number of visits at each vertex […]

The competition number of a generalized line graph is at most two

Park, Boram ; Sano, Yoshio.
In 1982, Opsut showed that the competition number of a line graph is at most two and gave a necessary and sufficient condition for the competition number of a line graph being one. In this paper, we generalize this result to the competition numbers of generalized line graphs, that is, we show that […]

On bipartite powers of bigraphs

Okamoto, Yoshio ; Otachi, Yota ; Uehara, Ryuhei.
The notion of graph powers is a well-studied topic in graph theory and its applications. In this paper, we investigate a bipartite analogue of graph powers, which we call bipartite powers of bigraphs. We show that the classes of bipartite permutation graphs and interval bigraphs are closed under […]

alpha-Labelings and the Structure of Trees with Nonzero alpha-Deficit

Brinkmann, Gunnar ; Crevals, Simon ; Melot, Hadrien ; Rylands, Leanne ; Steffen, Eckhard.
We present theoretical and computational results on alpha-labelings of trees. The theorems proved in this paper were inspired by the results of a computer investigation of alpha-labelings of all trees with up to 26 vertices, all trees with maximum degree 3 and up to 36 vertices, all trees with […]

The generalized 3-connectivity of Cartesian product graphs

Li, Hengzhe ; Li, Xueliang ; Sun, Yuefang.
The generalized connectivity of a graph, which was introduced by Chartrand et al. in 1984, is a generalization of the concept of vertex connectivity. Let S be a nonempty set of vertices of G, a collection \T-1, T (2), ... , T-r\ of trees in G is said to be internally disjoint trees connecting S if […]

Nordhaus-Gaddum Type Results for Total Domination

Henning, Michael,  ; Joubert, Ernst ; Southey, Justin.
A Nordhaus-Gaddum-type result is a (tight) lower or upper bound on the sum or product of a parameter of a graph and its complement. In this paper we study Nordhaus-Gaddum-type results for total domination. We examine the sum and product of γt(G1) and γt(G2) where G1 ⊕G2 = K(s,s), and γt is the total […]

On the number of factors in codings of three interval exchange

Ambrož, Petr ; Frid, Anna ; Masáková, Zuzana ; Pelantová, Edita.
We consider exchange of three intervals with permutation (3, 2, 1). The aim of this paper is to count the cardinality of the set 3iet (N) of all words of length N which appear as factors in infinite words coding such transformations. We use the strong relation of 3iet words and words coding exchange […]