Degree Conditions and Degree Bounded Trees

In this paper, we give sufficient conditions for a graph to have degree bounded trees. Let G be a connected graph and $A\subseteq V(G)$. We denote by ${\sigma }_k(A)$ the minimum value of the degree sum in G of any k pairwise nonadjacent vertices of A, and by $w(G-A)$ the number of components of the subgraph $G-A$ of G induced by $V(G)-A$. Our main results are the following: (i) If ${\sigma }_k(A)⩾|G|-1$, then G contains a tree T with maximum degree ⩽k and $A\subseteq V(T)$. (ii) If ${\sigma }_{k-w(G-A)}(A)⩾|A|-1$, then G contains a spanning tree T with $d_T(x)⩽k$ for any $x\in A$. These are generalizations of the result by S. Win [S. Win, Existenz von Gerüsten mit Vorgeschriebenem Maximalgrad in Graphen, Abh. Math. Seminar Univ. Humburg 43 (1975) 263–267] and degree conditions are sharp.     

On a tree-partition problem

If $T=(V,E)$ is a tree then – T denotes the additive hereditary property consisting of all graphs that does not contain T as a subgraph. For an arbitrary vertex v of T we deal with a partition of T into two trees $T_1$, $T_2$, so that $V(T_1)\cap V(T_2)=\{v\}$, $V(T_1)\cup (T_2)=V(T)$, $E(T_1)\cap E(T_2)=\varnothing$, $E(T_1)\cup E(T_2)=E(T)$, $T[V(T_1)\backslash \{v\}]\subseteq E(T_1)$ and $T[V(T_2)\backslash \{v\}]\subseteq E(T_2)$. We call such a partition a $T_v-partition$ of T. We study the following em: Given a graph G belonging to –T. Is it true that for any $T_v$-partition $T_1$, $T_2$ of T there exists a partition $\{V_1,V_2\}$ of the vertices of G such that $G[V_1]\in -T_1$ and $G[V_2]\in -T_2$? This problem provides a natural generalization of Δ-partition problem studied by L. Lovász ([L. Lovász, On decomposition of graphs. Studia Sci. Math. Hungar. 1 (1966) 237–238]) and Path Partition Conjecture formulated by P. Mihók ([P. Mihók, Problem 4, in: M. Borowiecki, Z. Skupien (Eds.), Graphs, Hypergraphs and Matroids, Zielona Góra, 1985, p. 86]). We present some partial results and a contribution to the Path Kernel Conjecture that was formulated with connection to Path Partition Conjecture.     

Generating all the Steiner trees and computing Steiner intervals for a fixed number of terminals

In this work we present an enumeration algorithm for the generation of all Steiner trees containing a given set W of terminals of an unweighted graph G such that $|W|=k$, for a fixed positive integer k. The enumeration is performed within $O(n)$ delay, where $n=|V(G)|$ consequence of the algorithm is that the Steiner interval and the strong Steiner interval of a subset $W\subseteq V(G)$ can be computed in polynomial time, provided that the size of W is bounded by a constant.     

Degree Sequence of Tight Distance Graphs

A graph G on n vertices is a tight distance graph if there exists a set $D\subseteq \{1,2,\dots ,n-1\}$ such that $V(G)=\{0,1,\dots ,n-1\}$ and $ij\in E(G)$ if and only if $|i-j|\in D$. A characterization of the degree sequences of tight distance graphs is given. This characterization yields a fast method for recognizing and realizing degree sequences of tight distance graphs.     

On Vertex Partitions and the Colin de Verdière Parameter

We study vertex partitions of graphs according to their Colin de Verdiere parameter μ. By a result of Ding et al. [DOSOO] we know that any graph G with $\mu (G)⩾2$ admits a vertex partition into two graphs with μ at most $\mu (G)-1$. Here we prove that any graph G with $\mu (G)⩾3$ admits a vertex partition into three graphs with μ at most $\mu (G)-2$. This study is extended to other minor-monotone graph parameters like the Hadwiger number.     

Power domination in certain chemical structures

Let $G(V,E)$ be a simple connected graph. A set $S\subseteq V$ is a power dominating set (PDS) of G, if every vertex and every edge in the system is observed following the observation rules of power system monitoring. The minimum cardinality of a PDS of a graph G is the power domination number ${\gamma }_p(G)$. In this paper, we establish a fundamental result that would provide a lower bound for the power domination number of a graph. Further, we solve the power domination problem in polyphenylene dendrimers, Rhenium Trioxide (ReO₃) lattices and silicate networks.     

Enumeration of simple complete topological graphs

A simple topological graph $T=(V(T),E(T))$ is a drawing of a graph in the plane, where every two edges have at most one common point (an end-point or a crossing) and no three edges pass through a single crossing. Topological graphs G and H are isomorphic if H can be obtained from G by a homeomorphism of the sphere, and weakly isomorphic if G and H have the same set of pairs of crossing edges. We prove that the number of isomorphism classes of simple complete topological graphs on n vertices is $2^{\mathrm{\Theta }(n^4)}$. We also show that the number weak isomorphism classes of simple complete topological graphs with n vertices and $\left(\begin{array}{c}\hfill n\hfill \\ \hfill 4\hfill \end{array}\right)$ crossings is at least $2^{n(\log n-O(1))}$, which improves the estimate of Harborth an Mengersen.