Sierpiński graphs as spanning subgraphs of Hanoi graphs

Hanoi graphs H _p ⁿ model the Tower of Hanoi game with p pegs and n discs. Sierpinski graphs S _p ⁿ arose in investigations of universal topological spaces and have meanwhile been studied extensively. It is proved that S _p ⁿ embeds as a spanning subgraph into H _p ⁿ if and only if p is odd or, trivially, if n = 1.     

On λ-harmonic graphs

A λ harmonic graph G, a λ-Hgraph G for short, means that there exists a constant denotes the degree of vertex vi. In this paper, some harmonic properties of the complement and line graph are given, and some algebraic properties for the λ-Hgraphs are obtained.     

On λ-harmonic graphs

A λ harmonic graph G, a λ-Hgraph G for short, means that there exists a constant A such that the equality λd（ui） = ∑（vi,vj）∈E（G） d（vj） holds for all i = 1, 2,…, ｜V（G）｜, where d（vi） denotes the degree of vertex vi. In this paper, some harmonic properties of the complement and line graph are given, and some algebraic properties for the λ-Hgraphs are obtained.     

Lovász–Schrijver SDP-operator,near-perfect graphs and near-bipartite graphs

We study the Lovász–Schrijver lift-and-project operator (\({{\mathrm{\text {LS}}}}_+\)) based on the cone of symmetric, positive semidefinite matrices, applied to the fractional stable set polytope of graphs. The problem of obtaining a combinatorial characterization of graphs for which the \({{\mathrm{\text {LS}}}}_+\)-operator generates the stable set polytope in one step has been open since 1990. We call these graphs \({{{\mathrm{\text {LS}}}}}_+\)-perfect. In the current contribution, we pursue a full combinatorial characterization of \({{{\mathrm{\text {LS}}}}}_+\)-perfect graphs and make progress towards such a characterization by establishing a new, close relationship among \({{{\mathrm{\text {LS}}}}}_+\)-perfect graphs, near-bipartite graphs and a newly introduced concept of full-support-perfect graphs.     

On k-critical 2k-connected graphs

A graph G is called an (n, k)-graph if k(G - S) = n - |S| for any S V(G) with |S| ≤ k, where k.(G) denotes the connectivity of G. Mader conjectured that for k ≥ 3 the graph K2k+2 - (1-factor) is the unique (2k, k)-graph. Kriesell has settled two special cases for k = 3, 4. We prove the conjecture for the general case k ≥ 5.     

Vertex partitions of r-edge-colored graphs

Let G be an edge-colored graph.The monochromatic tree partition problem is to find the minimum number of vertex disjoint monochromatic trees to cover the all vertices of G.In the authors' previous work,it has been proved that the problem is NP-complete and there does not exist any constant factor approximation algorithm for it unless P=NP.In this paper the authors show that for any fixed integer r≥5,if the edges of a graph G are colored by r colors,called an r-edge-colored graph,the problem remains NP-complete.Similar result holds for the monochromatic path(cycle)partition problem.Therefore,to find some classes of interesting graphs for which the problem can be solved in polynomial time seems interesting. A linear time algorithm for the monochromatic path partition problem for edge-colored trees is given.     

Equitable Δ-coloring of graphs

Consider a graph $G$ consisting of a vertex set $V\left(G\right)$ and an edge set $E\left(G\right)$. Let $\Delta \left(G\right)$ and $\chi \left(G\right)$ denote the maximum degree and the chromatic number of $G$, respectively. We say that $G$ is equitably $\Delta \left(G\right)$-colorable if there exists a proper $\Delta \left(G\right)$-coloring of $G$ such that the sizes of any two color classes differ by at most one. Obviously, if $G$ is equitably $\Delta \left(G\right)$-colorable, then $\Delta \left(G\right)\ge \chi \left(G\right)$. Conversely, even if $G$ satisfies $\Delta \left(G\right)\ge \chi \left(G\right)$, we cannot guarantee that $G$ must be equitably $\Delta \left(G\right)$-colorable. In 1994, the Equitable $\Delta$-Coloring Conjecture $\left(E\Delta \mathrm{CC}\right)$ asserts that a connected graph $G$ with $\Delta \left(G\right)\ge \chi \left(G\right)$ is equitably $\Delta \left(G\right)$-colorable if $G$ is different from $K_{2n+1,2n+1}$ for all $n\ge 1$. In this paper, we give necessary conditions for a graph $G$ (not necessarily connected) with $\Delta \left(G\right)\ge \chi \left(G\right)$ to be equitably $\Delta \left(G\right)$-colorable and prove that those necessary conditions are also sufficient conditions when $G$ is a bipartite graph, or $G$ satisfies $\Delta \left(G\right)\ge \frac{\left|V\left(G\right)\right|}{3}+1$, or $G$ satisfies $\Delta \left(G\right)\le 3$.     

k L-list λ colouring of graphs

The k L-list λ colouring of a graph G is an L-list colouring (with positive integers) where any two colours assigned to adjacent vertices do not belong to a set λ, where the avoided assignments are listed. Moreover, the length of the list L(x), for every vertex x of G, must be less than or equal to a positive integer k, where k is the number of colours. This problem is NP-complete and we present an efficient heuristic algorithm to solve it. A fundamental aspect of the algorithm we developed is a particular technique of backtracking that permits the direct reassignment of the vertices causing the conflict if, at the moment of assigning a colour to a vertex, no colour on the list associated to it is available. An application of this algorithm to the problem of assigning arriving or leaving trains to the available tracks at a railway station is also discussed.     

DNA labelled graphs with DNA computing

Let k≥2, 1≤i≤k andα≥1 be three integers. For any multiset which consists of some k-long oligonucleotides, a DNA labelled graph is defined as follows: each oligonucleotide from the multiset becomes a point; two points are connected by an arc from the first point to the second one if the i rightmost uucleotides of the first point overlap with the i leftmost nucleotides of the second one. We say that a directed graph D can be(k, i;α)-labelled if it is possible to assign a label(l_1(x),..., l_k(x))to each point x of D such that l_j(x)∈{0,...,a-1}for any j∈{1,...,k}and(x,y)∈E(D)if and only if(l_k-i 1(x),..., l_k(x))=(l_1(y),..., l_i(y)). By the biological background, a directed graph is a DNA labelled graph if there exist two integers k, i such that it is(k, i; 4)-labelled. In this paper, a detailed discussion of DNA labelled graphs is given. Firstly, we study the relationship between DNA labelled graphs and some existing directed graph classes. Secondly, it is shown that for any DNA labelled graph, there exists a positive integer i such that it is(2i, i; 4)-labelled. Furthermore, the smallest i is determined, and a polynomial-time algorithm is introduced to give a(2i, i; 4)-labelling for a given DNA labelled graph. Finally, a DNA algorithm is given to find all paths from one given point to another in a(2i, i; 4)-labelled directed graph.     

Hamiltonian cycles in I–graphs

The I–graphs generalize the family of generalized Petersen graphs. We show that a connected I–graph which is not a generalized Petersen graph is Hamiltonian.     

Turán-type bounds for distance graphs

A lower bound is obtained for the number of edges in a distance graph G in an infinitesimal plane layer ?² × [0, ε] ^d , which relates the number of edges e(G), the number of vertices ν(G), and the independence number α(G). It is proved that \(e\left( G \right) \geqslant \frac{{19\nu \left( G \right) - 50\alpha \left( G \right)}}{3}\). This result generalizes a previous bound for distance graphs in the plane. It substantially improves Turán’s bound in the case where \(\frac{1}{5} \leqslant \frac{{\alpha \left( G \right)}}{{\nu \left( G \right)}} \leqslant \frac{2}{7}\).     

On the adjacent-vertex-strongly-distinguishing total coloring of graphs

For any vertex u∈V(G), let T_N(U)={u}∪{uv|uv∈E(G), v∈v(G)}∪{v∈v(G)|uv∈E(G)}and let f be a total k-coloring of G. The total-color neighbor of a vertex u of G is the color set C_f(u)={f(x)|x∈TN(U)}. For any two adjacent vertices x and y of V(G)such that C_f(x)≠C_f(y), we refer to f as a k-avsdt-coloring of G("avsdt"is the abbreviation of"adjacent-vertex-strongly- distinguishing total"). The avsdt-coloring number of G, denoted by X_(ast)(G), is the minimal number of colors required for a avsdt-coloring of G. In this paper, the avsdt-coloring numbers on some familiar graphs are studied, such as paths, cycles, complete graphs, complete bipartite graphs and so on. We proveΔ(G) 1≤X_(ast)(G)≤Δ(G) 2 for any tree or unique cycle graph G.