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

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.     

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.     

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.     

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.     

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.     

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}\).     

Distance–regular graphs having the M-property

We analyse when the Moore–Penrose inverse of the combinatorial Laplacian of a distance–regular graph is an M-matrix; that is, it has non-positive off-diagonal elements or, equivalently when the Moore–Penrose inverse of the combinatorial Laplacian of a distance–regular graph is also the combinatorial Laplacian of another network. When this occurs we say that the distance–regular graph has the M-property. We prove that only distance–regular graphs with diameter up to three can have the M-property and we give a characterization of the graphs that satisfy the M-property in terms of their intersection array. Moreover, we exhaustively analyse strongly regular graphs having the M-property and we give some families of distance–regular graphs with diameter three that satisfy the M-property. Roughly speaking, we prove that all distance–regular graphs with diameter one; about half of the strongly regular graphs; only some imprimitive distance–regular graphs with diameter three, and no distance–regular graphs with diameter greater than three, have the M-property. In addition, we conjecture that no primitive distance–regular graph with diameter three has the M-property.