On edge-primitive graphs of order twice a prime power

A graph is called edge-primitive if its automorphism group acts primitively on its edge set. In this paper, edge-primitive graphs of order twice a prime power are completely determined.     

Edge partitions of optimal 2-plane and 3-plane graphs

A topological graph is a graph drawn in the plane. A topological graph is $k$-plane, $k>0$, if each edge is crossed at most $k$ times. We study the problem of partitioning the edges of a $k$-plane graph such that each partite set forms a graph with a simpler structure. While this problem has been studied for $k=1$, we focus on optimal 2-plane and on optimal 3-plane graphs, which are 2-plane and 3-plane graphs with maximum density. We prove the following results. (i) It is not possible to partition the edges of a simple (i.e., with neither self-loops nor parallel edges) optimal 2-plane graph into a 1-plane graph and a forest, while (ii) an edge partition formed by a 1-plane graph and two plane forests always exists and can be computed in linear time. (iii) There exist efficient algorithms to partition the edges of a simple optimal 2-plane graph into a 1-plane graph and a plane graph with maximum vertex degree at most 12, or with maximum vertex degree at most 8 if the optimal2-plane graph is such that its crossing-free edges form a graph with no separating triangles. (iv) There exists an infinite family of simple optimal 2-plane graphs such that in any edge partition composed of a 1-plane graph and a plane graph, the plane graph has maximum vertex degree at least 6 and the 1-plane graph has maximum vertex degree at least 12. (v) Every optimal 3-plane graph whose crossing-free edges form a biconnected graph can be decomposed, in linear time, into a 2-plane graph and two plane forests.     

Oriented colourings of graphs with maximum degree three and four

We show that any orientation of a graph with maximum degree three has an oriented 9-colouring, and that any orientation of a graph with maximum degree four has an oriented 69-colouring. These results improve the best known upper bounds of 11 and 80, respectively.     

Edge decompositions and rooted packings of graphs

Let H be a fixed graph. In this paper we consider the problem of edge decomposition of a graph into subgraphs isomorphic to H or $2K_2$ (a 2-edge matching). We give a partial classification of the problems of existence of such decomposition according to the computational complexity. More specifically, for some large class of graphs H we show that this problem is polynomial time solvable and for some other large class of graphs it is NP-complete. These results can be viewed as some edge decomposition analogs of a result by Loebl and Poljak who classified according to the computational complexity the problem of existence of a graph factor with components isomorphic to H or $K_2$. In the proofs of our results we apply so-called rooted packings into graphs which are mutual generalizations of both edge decompositions and factors of graphs.     

The graphs that have antivoltages using groups of small order

Given a group $\Gamma$ of order at most six, we characterize the graphs that have $\Gamma$-antivoltages and also determine the list of minor-minimal graphs that have no $\Gamma$-antivoltage. Our characterizations yield polynomial-time recognition algorithms for such graphs.     

A comparison of several nearest neighbor classifier metrics using Tabu Search algorithm for the feature selection problem

The feature selection problem is an interesting and important topic which is relevant for a variety of database applications. This paper utilizes the Tabu Search metaheuristic algorithm to implement a feature subset selection procedure while the nearest neighbor classification method is used for the classification task. Tabu Search is a general metaheuristic procedure that is used in order to guide the search to obtain good solutions in complex solution spaces. Several metrics are used in the nearest neighbor classification method, such as the euclidean distance, the Standardized Euclidean distance, the Mahalanobis distance, the City block metric, the Cosine distance and the Correlation distance, in order to identify the most significant metric for the nearest neighbor classifier. The performance of the proposed algorithms is tested using various benchmark datasets from UCI Machine Learning Repository.     

Edge coloring of graphs with small maximum degrees

By applying a discharging method, we give new lower bounds for the sizes of edge chromatic critical graphs for small maximum degrees. Furthermore, it is also proved that if G is a graph embeddable in a surface S with characteristic c_S=−4 or −5 or −6, then G is class one if its maximum degree Δ≥10 or 11 or 12 respectively.     

Periodic motions of a class of forced infinite lattices with nearest neighbor interaction

In this paper, by using a priori bounds, topological degree and limiting arguments, we study the existence of periodic solutions of a class of one-dimensional chain of particles periodically perturbed and with nearest neighbor interaction between particles. We study the necessary and sufficient conditions for the existence of periodic solutions in two cases when the number of particles is finite and infinite and obtain different results.     

List neighbor sum distinguishing edge coloring of subcubic graphs

A proper $k$-edge-coloring of a graph with colors in $\{1,2,\dots ,k\}$ is neighbor sum distinguishing (or, NSD for short) if for any two adjacent vertices, the sums of the colors of the edges incident with each of them are distinct. Flandrin et al. conjectured that every connected graph with at least $6$ vertices has an NSD edge coloring with at most $\Delta +2$ colors. Huo et al. proved that every subcubic graph without isolated edges has an NSD $6$-edge-coloring. In this paper, we first prove a structural result about subcubic graphs by applying the decomposition theorem of Trotignon and Vu?kovi?, and then applying this structural result and the Combinatorial Nullstellensatz, we extend the NSD $6$-edge-coloring result to its list version and show that every subcubic graph without isolated edges has a list NSD $6$-edge-coloring.     

Antimagic orientations of disconnected even regular graphs

A $labeling$ of a digraph $D$ with $m$ arcs is a bijection from the set of arcs of $D$ to $\{1,2,\dots ,m\}$. A labeling of $D$ is $antimagic$ if no two vertices in $D$ have the same vertex-sum, where the vertex-sum of a vertex $u\in V\left(D\right)$ for a labeling is the sum of labels of all arcs entering $u$ minus the sum of labels of all arcs leaving $u$. An orientation $D$ of a graph $G$ is $antimagic$ if $D$ has an antimagic labeling. Hefetz et al. (2010) raised the question: Does every graph admit an antimagic orientation? It had been proved that every 2$d$-regular graph with at most two odd components has an antimagic orientation. In this paper, we consider 2$d$-regular graphs with more than two odd components. We show that every 2$d$-regular graph with $k(3\le k\le 5d+4)$ odd components has an antimagic orientation. And we show that each 2$d$-regular graph with $k(k\ge 5d+5)$ odd components admits an antimagic orientation if each odd component has at least $2x_0+5$ vertices with $x_0=?\frac{k?(5d+4)}{2d?2}?$.     

Antimagic orientation of Halin graphs

An antimagic labeling of a digraph $D$ with $n$ vertices and $m$ arcs is a bijection from the set of arcs of $D$ to $\{1,2,\dots ,m\}$ such that all $n$ oriented vertex sums are pairwise distinct, where an oriented vertex sum of a vertex is the sum of labels of all arcs entering that vertex minus the sum of labels of all arcs leaving it. Hefetz, Mütze and Schwartz conjectured every connected undirected graph admits an antimagic orientation. In this paper, we support this conjecture by proving that every Halin graph admits an antimagic orientation.     

On factor-invariant graphs

We classify trivalent vertex-transitive graphs whose edge sets have a partition into a Hamilton cycle and a 1-factor that is invariant under the action of the full automorphism group.     

New concepts of regular and (highly) irregular vague graphs with applications

In this paper, some types of vague graphs are introdaced such as $d_m$-regular, $t{d}_m$-regular, $m$-highly irregular and $m$-highly totally irregular vague graphs are introduced and some properties of them are discussed. Comparative study between $d_m$-regular ($m$-highly irregular) vague graph and $t{d}_m$-regular ($m$-highly totally irregular) vague graph are done. In addition, $d_m$-regularity and $m$-highly irregularity on some vague graphs, which underlying crisp graphs are a cycle or a path is also studied. Finally, some applications of regular vague graphs are given for demonstration of fullerene molecules, road transport network and wireless multihop networks.     

Edge choosability of planar graphs without 5-cycles with a chord

Let G be a plane graph having no 5-cycles with a chord. If either Δ≥6, or Δ=5 and G contains no 4-cycles with a chord or no 6-cycles with a chord, then G is edge-(Δ+1)-choosable, where Δ denotes the maximum degree of G.     

On incidence choosability of cubic graphs

An incidence of a graph $G$ is a pair $(u,e)$ where $u$ is a vertex of $G$ and $e$ is an edge of $G$ incident to $u$. Two incidences $(u,e)$ and $(v,f)$ of $G$ are adjacent whenever (i) $u=v$, or (ii) $e=f$, or (iii) $uv=e$ or $uv=f$. An incidence$k$-coloring of $G$ is a mapping from the set of incidences of $G$ to a set of $k$ colors such that every two adjacent incidences receive distinct colors. The notion of incidence coloring has been introduced by Brualdi and Quinn Massey (1993) from a relation to strong edge coloring, and since then, has attracted a lot of attention by many authors.On a list version of incidence coloring, it was shown by Benmedjdoub et al. (2017) that every Hamiltonian cubic graph is incidence 6-choosable. In this paper, we show that every cubic (loopless) multigraph is incidence 6-choosable. As a direct consequence, it implies that the list strong chromatic index of a $(2,3)$-bipartite graph is at most 6, where a (2,3)-bipartite graph is a bipartite graph such that one partite set has maximum degree at most 2 and the other partite set has maximum degree at most 3.     

Rainbow spanning tree decompositions in complete graphs colored by cyclic 1-factorizations

Brualdi and Hollingsworth conjectured in Brualdi and Hollingsworth (1996) that in any complete graph $K_{2n}$, $n\ge 3$, which is properly colored with $2n?1$ colors, the edge set can be partitioned into $n$ edge disjoint rainbow spanning trees (where a graph is said to be rainbow if its edges have distinct colors). Constantine (2002) strengthened this conjecture asking the rainbow spanning trees to be pairwise isomorphic. He also showed an example satisfying his conjecture for every $2n\in \{2^s:s\ge 3\}\cup \{5?2^s,s\ge 1\}$ . Caughmann, Krussel and Mahoney (2017) recently showed a first infinite family of edge colorings for which the conjecture of Brualdi and Hollingsworth can be verified. In the present paper, we extend this result to all edge-colorings arising from cyclic 1-factorizations of $K_{2n}$ constructed by Hartman and Rosa (1985). Finally, we remark that our constructions permit to extend Constatine’s result also to all $2n\in \{2^{s}d:s\ge 1,d>3\text{odd}\}$.     

Edge intersection graphs of linear 3-uniform hypergraphs

Let be the class of edge intersection graphs of linear 3-uniform hypergraphs. It is known that the problem of recognition of the class is NP-complete. We prove that this problem is polynomially solvable in the class of graphs with minimum vertex degree ≥10. It is also proved that the class is characterized by a finite list of forbidden induced subgraphs in the class of graphs with minimum vertex degree ≥16.     

Adjacent vertex distinguishing total coloring of planar graphs with maximum degree 9

Let $k$ be a positive integer. An adjacent vertex distinguishing (for short, AVD) total-$k$-coloring of a graph $G$ is a proper total-$k$-coloring of $G$ such that any two adjacent vertices have different color sets, where the color set of a vertex $v$ contains the color of $v$ and the colors of its incident edges. It was conjectured that any graph with maximum degree $\Delta$ has an AVD total-($\Delta +3$)-coloring. The conjecture was confirmed for any graph with maximum degree at most 4 and any planar graph with maximum degree at least 10. In this paper, we verify the conjecture for all planar graphs with maximum degree at least 9. Moreover, we prove that any planar graph with maximum degree at least 10 has an AVD total-($\Delta +2$)-coloring and the bound $\Delta +2$ is sharp.     

Highly-connected planar cubic graphs with few or many Hamilton cycles

In this paper we consider the number of Hamilton cycles in planar cubic graphs of high cyclic edge-connectivity, answering two questions raised by Chia and Thomassen (2012) about extremal graphs in these families. In particular, we find families of cyclically 5-edge-connected planar cubic graphs with more Hamilton cycles than the generalized Petersen graphs $P(2n,2)$. The graphs themselves are fullerene graphs that correspond to certain carbon molecules known as nanotubes—more precisely, the family consists of the zigzag nanotubes of (fixed) width 5and increasing length. In order to count the Hamilton cycles in the nanotubes, we develop methods inspired by the transfer matrices of statistical physics. We outline how these methods can be adapted to count the Hamilton cycles in nanotubes of greater (but still fixed) width, with the caveat that the resulting expressions involve matrix powers. We also consider cyclically 4-edge-connected planar cubic graphs with few Hamilton cycles, and exhibit an infinite family of such graphs each with exactly 4 Hamilton cycles. Finally we consider the “other extreme” for these two classes of graphs, thus investigating cyclically 4-edge-connected planar cubic graphs with many Hamilton cycles and the cyclically 5-edge-connected planar cubic graphs with few Hamilton cycles. In each of these cases, we present partial results, examples and conjectures regarding the graphs with few or many Hamilton cycles.