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

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

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

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

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

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

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

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

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

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

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 […]

### Matchings of quadratic size extend to long cycles in hypercubes

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)$ […]

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

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 […]

### Heredity for generalized power domination

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

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 […]

### Traceability of locally hamiltonian and locally traceable graphs

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

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

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 […]

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

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 […]

### Edge Disjoint Hamilton Cycles in Knödel Graphs

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 […]

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

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 […]

### Connected Tropical Subgraphs in Vertex-Colored Graphs

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

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 […]

### Rainbow eulerian multidigraphs and the product of cycles

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 […]

### Edge-partitioning graphs into regular and locally irregular components

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

An oriented graph $øverrightarrow{G}$ is said weak (resp. strong) if, for every pair $\{ u,v \}$ of vertices of $øverrightarrow{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 length […]

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

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

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.

### Cubical coloring — fractional covering by cuts and semidefinite programming

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. […]

### Strong parity vertex coloring of plane graphs

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

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, […]

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

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 […]

### A variant of Niessen’s problem on degreesequences of graphs

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 Hamiltonian Paths and Cycles in Sufficiently Large Distance Graphs

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 […]

### The Price of Connectivity for Vertex Cover

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

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). […]

### On the Meyniel condition for hamiltonicity in bipartite digraphs

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 size, radius and minimum degree

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 generalized 3-connectivity of Lexicographic product graphs

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 […]

### Efficient open domination in graph products

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 […]

### Generalized dynamic storage allocation

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

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

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

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 […]

### Complexity of conditional colouring with given template

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

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

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 […]

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

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

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 […]

### Balancedness of subclasses of circular-arc graphs

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, […]

### Removable edges in near-bricks

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. […]

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

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 […]

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

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 […]

### Maximal independent sets in bipartite graphs with at least one cycle

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 […]

### Bipartite powers of k-chordal graphs

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. […]

### Improved bounds on the crossing number of butterfly network

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.

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

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 […]

### The resolving number of a graph Delia

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 […]

### Clique cycle transversals in graphs with few P₄'s

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 […]

### A new characterization and a recognition algorithm of Lucas cubes

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 […]

### Krausz dimension and its generalizations in special graph classes

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 […]

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

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→ℕ. […]

### Further results on maximal nontraceable graphs of smallest size

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 […]

### All totally symmetric colored graphs

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, […]

### The b-chromatic number of powers of cycles

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 […]

### The determining number of Kneser graphs

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

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, […]

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

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

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 […]

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

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

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 […]

### On 4-valent Frobenius circulant graphs

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 […]

### A note on planar Ramsey numbers for a triangle versus wheels

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.

### Secure frameproof codes through biclique covers

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 […]

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

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 […]

### Graphs with many vertex-disjoint cycles

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 […]

### Random Cayley digraphs of diameter 2 and given degree

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 […]

### Immersion containment and connectivity in color-critical graphs

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

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 […]

### Upper k-tuple domination in graphs

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 […]

### Nordhaus-Gaddum Type Results for Total Domination

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

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 […]