An Ore-type condition for arbitrarily vertex decomposable graphs

Let G be a graph of order n and r, 1≤r≤n, a fixed integer. G is said to be r-vertex decomposable if for each sequence (n₁,…,n_r) of positive integers such that n₁+?+n_r=n there exists a partition (V₁,…,V_r) of the vertex set of G such that for each i∈{1,…,r}, V_i induces a connected subgraph of G on n_i vertices. G is called arbitrarily vertex decomposable if it is r-vertex decomposable for each r∈{1,…,n}.In this paper we show that if G is a connected graph on n vertices with the independence number at most ⌈n/2⌉ and such that the degree sum of any pair of non-adjacent vertices is at least n−3, then G is arbitrarily vertex decomposable or isomorphic to one of two exceptional graphs. We also exhibit the integers r for which the graphs verifying the above degree-sum condition are not r-vertex decomposable.     

Partitioning complete graphs by heterochromatic trees

A heterochromatic tree is an edge-colored tree in which any two edges have different colors. The heterochromatic tree partition number of an r-edge-colored graph G, denoted by t _r (G), is the minimum positive integer p such that whenever the edges of the graph G are colored with r colors, the vertices of G can be covered by at most p vertex-disjoint heterochromatic trees. In this paper we determine the heterochromatic tree partition number of r-edge-colored complete graphs. We also find at most t _r (K _n ) vertex-disjoint heterochromatic trees to cover all the vertices in polynomial time for a given r-edge-coloring of K _n .     

A linear algorithm for minimum 1-identifying codes in oriented trees

Consider an oriented graph G=(V,A), a subset of vertices C⊆V, and an integer r?1; for any vertex v∈V, let denote the set of all vertices x such that there exists a path from x to v with at most r arcs. If for all vertices v∈V, the sets are all nonempty and different, then we call C an r-identifying code. We describe a linear algorithm which gives a minimum 1-identifying code in any oriented tree.     

Reconstructing edge-disjoint paths

For an undirected graph G=(V,E), the edge connectivity values between every pair of nodes of G can be succinctly recorded in a flow-equivalent tree that contains the edge connectivity value for a linear number of pairs of nodes. We generalize this result to show how we can efficiently recover a maximum set of disjoint paths between any pair of nodes of G by storing such sets for a linear number of pairs of nodes. At the heart of our result is an observation that combining two flow solutions of the same value, one between nodes s and r and the second between nodes r and t, into a feasible flow solution of value f between nodes s and t, is equivalent to solving a stable matching problem on a bipartite multigraph.Our observation, combined with an observation of Chazelle, leads to a data structure, which takes O(n^3.5) time to generate, that can construct the maximum number λ(u,v) of edge-disjoint paths between any pair (u,v) of nodes in time O(α(n,n)λ(u,v)n) time.     

Quasi-kernels and quasi-sinks in infinite graphs

Given a directed graph G=(V,E) an independent set A⊂V is called quasi-kernel (quasi-sink) iff for each point v there is a path of length at most 2 from some point of A to v (from v to some point of A). Every finite directed graph has a quasi-kernel. The plain generalization for infinite graphs fails, even for tournaments. We study the following conjecture: for any digraph G=(V,E) there is a a partition (V₀,V₁) of the vertex set such that the induced subgraph G[V₀] has a quasi-kernel and the induced subgraph G[V₁] has a quasi-sink.     

Relative length of longest paths and longest cycles in triangle-free graphs

In this paper, we study triangle-free graphs. Let G=(V,E) be an arbitrary triangle-free graph with minimum degree at least two and σ₄(G)?|V(G)|+2. We first show that either for any path P in G there exists a cycle C such that |V_P?V_C|?1, or G is isomorphic to exactly one exception. Using this result, we show that for any set S of at most δ vertices in G there is a cycle C such that S⊆V_C.     

Transitive orientations in bull-reducible Berge graphs

A bull is a graph with five vertices r,y,x,z,s and five edges ry, yx, yz, xz, zs. A graph G is bull-reducible if every vertex of G lies in at most one bull of G. We prove that every bull-reducible Berge graph G that contains no antihole is weakly chordal, or has a homogeneous set, or is transitively orientable. This yields a fast polynomial time algorithm to color the vertices of such a graph exactly.     

Clique-inserted-graphs and spectral dynamics of clique-inserting

Motivated by studying the spectra of truncated polyhedra, we consider the clique-inserted-graphs. For a regular graph G of degree r>0, the graph obtained by replacing every vertex of G with a complete graph of order r is called the clique-inserted-graph of G, denoted as C(G). We obtain a formula for the characteristic polynomial of C(G) in terms of the characteristic polynomial of G. Furthermore, we analyze the spectral dynamics of iterations of clique-inserting on a regular graph G. For any r-regular graph G with r>2, let S(G) denote the union of the eigenvalue sets of all iterated clique-inserted-graphs of G. We discover that the set of limit points of S(G) is a fractal with the maximum r and the minimum −2, and that the fractal is independent of the structure of the concerned regular graph G as long as the degree r of G is fixed. It follows that for any integer r>2 there exist infinitely many connected r-regular graphs (or, non-regular graphs with r as the maximum degree) with arbitrarily many distinct eigenvalues in an arbitrarily small interval around any given point in the fractal. We also present a formula on the number of spanning trees of any kth iterated clique-inserted-graph and other related results.     

An upper bound for the restrained domination number of a graph with minimum degree at least two in terms of order and minimum degree

Let G=(V,E) be a graph. A set S⊆V is a restrained dominating set if every vertex in V−S is adjacent to a vertex in S and to a vertex in V−S. The restrained domination number of G, denoted γ_r(G), is the smallest cardinality of a restrained dominating set of G. We will show that if G is a connected graph of order n and minimum degree δ and not isomorphic to one of nine exceptional graphs, then .     

Planar unit-distance graphs having planar unit-distance complement

A graph G=(V,E) is called a unit-distance graph in the plane if there is an embedding of V into the plane such that every pair of adjacent vertices are at unit distance apart. If an embedding of V satisfies the condition that two vertices are adjacent if and only if they are at unit distance apart, then G is called a strict unit-distance graph in the plane. A graph G is a (strict) co-unit-distance graph, if both G and its complement are (strict) unit-distance graphs in the plane. We show by an exhaustive enumeration that there are exactly 69 co-unit-distance graphs (65 are strict co-unit-distance graphs), 55 of which are connected (51 are connected strict co-unit-distance graphs), and seven are self-complementary.     

On the sizes of graphs and their powers: The undirected case

Let G be an undirected graph and G^r be its r-th power. We study different issues dealing with the number of edges in G and G^r. In particular, we answer the following question: given an integer r≥2 and all connected graphs G of order n such that G^r≠K_n, what is the minimum number of edges that are added when going from G to G^r, and which are the graphs achieving this bound?     

Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs

A locally connected spanning tree of a graph G is a spanning tree T of G such that the set of all neighbors of v in T induces a connected subgraph of G for every v∈V(G). The purpose of this paper is to give linear-time algorithms for finding locally connected spanning trees on strongly chordal graphs and proper circular-arc graphs, respectively.     

Non-separating 2-factors of an even-regular graph

For a 2-factor F of a connected graph G, we consider G−F, which is the graph obtained from G by removing all the edges of F. If G−F is connected, F is said to be a non-separating 2-factor. In this paper we study a sufficient condition for a 2r-regular connected graph G to have such a 2-factor. As a result, we show that a 2r-regular connected graph G has a non-separating 2-factor whenever the number of vertices of G does not exceed 2r²+r.     

Polynomial algorithm for sharp upper bound of rainbow connection number of maximal outerplanar graphs

For a finite simple edge-colored connected graph G (the coloring may not be proper), a rainbow path in G is a path without two edges colored the same; G is rainbow connected if for any two vertices of G, there is a rainbow path connecting them. Rainbow connection number, rc(G), of G is the minimum number of colors needed to color its edges such that G is rainbow connected. Chakraborty et al. (2011) [5] proved that computing rc(G) is NP-hard and deciding if rc(G)=2 is NP-complete. When edges of G are colored with fixed number k of colors, Kratochvil [6] proposed a question: what is the complexity of deciding whether G is rainbow connected? is this an FPT problem? In this paper, we prove that any maximal outerplanar graph is k rainbow connected for suitably large k and can be given a rainbow coloring in polynomial time.     

On bipartite zero-divisor graphs

A (finite or infinite) complete bipartite graph together with some end vertices all adjacent to a common vertex is called a complete bipartite graph with a horn. For any bipartite graph G, we show that G is the graph of a commutative semigroup with 0 if and only if it is one of the following graphs: star graph, two-star graph, complete bipartite graph, complete bipartite graph with a horn. We also prove that a zero-divisor graph is bipartite if and only if it contains no triangles. In addition, we give all corresponding zero-divisor semigroups of a class of complete bipartite graphs with a horn and determine which complete r-partite graphs with a horn have a corresponding semigroup for r≥3.     

On bijections that preserve complementarity of subspaces

The set G of all m-dimensional subspaces of a 2m-dimensional vector space V is endowed with two relations, complementarity and adjacency. We consider bijections from G onto G^′, where G^′ arises from a 2m^′-dimensional vector space V^′. If such a bijection ? and its inverse leave one of the relations from above invariant, then also the other. In case m?2 this yields that ? is induced by a semilinear bijection from V or from the dual space of V onto V^′.As far as possible, we include also the infinite-dimensional case into our considerations.     

Spanning trails containing given edges

A graph G is Eulerian-connected if for any u and v in V(G), G has a spanning (u,v)-trail. A graph G is edge-Eulerian-connected if for any e^′ and e^″ in E(G), G has a spanning (e^′,e^″)-trail. For an integer r?0, a graph is called r-Eulerian-connected if for any X⊆E(G) with |X|?r, and for any , G has a spanning (u,v)-trail T such that X⊆E(T). The r-edge-Eulerian-connectivity of a graph can be defined similarly. Let θ(r) be the minimum value of k such that every k-edge-connected graph is r-Eulerian-connected. Catlin proved that θ(0)=4. We shall show that θ(r)=4 for 0?r?2, and θ(r)=r+1 for r?3. Results on r-edge-Eulerian connectivity are also discussed.     

Edge degrees and dominating cycles

The edge degree d(e) of the edge e=uv is defined as the number of neighbours of e, i.e., |N(u)∪N(v)|-2. Two edges are called remote if they are disjoint and there is no edge joining them. In this article, we prove that in a 2-connected graph G, if d(e₁)+d(e₂)>|V(G)|-4 for any remote edges e₁,e₂, then all longest cycles C in G are dominating, i.e., G-V(C) is edgeless. This lower bound is best possible.As a corollary, it holds that if G is a 2-connected triangle-free graph with σ₂(G)>|V(G)|/2, then all longest cycles are dominating.     

Acyclic 5-choosability of planar graphs with neither 4-cycles nor chordal 6-cycles

A proper vertex coloring of a graph G=(V,E) is acyclic if G contains no bicolored cycle. A graph G is acyclically L-list colorable if for a given list assignment L={L(v):v∈V}, there exists a proper acyclic coloring ? of G such that ?(v)∈L(v) for all v∈V(G). If G is acyclically L-list colorable for any list assignment with |L(v)|≥k for all v∈V, then G is acyclically k-choosable. In this paper it is proved that every planar graph with neither 4-cycles nor chordal 6-cycles is acyclically 5-choosable. This generalizes the results of [M. Montassier, A. Raspaud, W. Wang, Acyclic 5-choosability of planar graphs without small cycles, J. Graph Theory 54 (2007) 245-260], and a corollary of [M. Montassier, P. Ochem, A. Raspaud, On the acyclic choosability of graphs, J. Graph Theory 51 (4) (2006) 281-300].