Incidence coloring of the squares of some graphs

The incidence chromatic number of G, denoted by χ_i(G), is the least number of colors such that G has an incidence coloring. In this paper, we determine the incidence chromatic number of the powers of paths, trees, which are min{n,2k+1}, and Δ(T²)+1, respectively. For the square of a Halin graph, we give an upper bound of its incidence chromatic number.     

Decomposing graphs into paths of fixed length

Barát and Thomassen have conjectured that, for any fixed tree T, there exists a natural number k _T such that the following holds: If G is a k _T -edge-connected graph such that |E(T)| divides |E(G)|, then G has a T-decomposition. The conjecture is trivial when T has one or two edges. Before submission of this paper, the conjecture had been verified only for two other trees: the paths of length 3 and 4, respectively. In this paper we verify the conjecture for each path whose length is a power of 2.     

Nonrepetitive colorings of trees

A coloring of the vertices of a graph G is nonrepetitive if no path in G forms a sequence consisting of two identical blocks. The minimum number of colors needed is the Thue chromatic number, denoted by π(G). A famous theorem of Thue asserts that π(P)=3 for any path P with at least four vertices. In this paper we study the Thue chromatic number of trees. In view of the fact that π(T) is bounded by 4 in this class we aim to describe the 4-chromatic trees. In particular, we study the 4-critical trees which are minimal with respect to this property. Though there are many trees T with π(T)=4 we show that any of them has a sufficiently large subdivision H such that π(H)=3. The proof relies on Thue sequences with additional properties involving palindromic words. We also investigate nonrepetitive edge colorings of trees. By a similar argument we prove that any tree has a subdivision which can be edge-colored by at most Δ+1 colors without repetitions on paths.     

The starlike trees with maximum and minimum second order connectivity index

Let G be a simple graph and h≥0 be an integer. The higher order connectivity index R _h (G) of G is defined as $$R_h(G)=\sum_{v_{i_1}v_{i_2}\cdots v_{i_{h+1}}} \frac{1}{\sqrt {d_{i_1}d_{i_2}\cdots d_{i_{h+1}}}},$$ where d _i denotes the degree of the vertex v _i and $v_{i_{1}}v_{i_{2}}\cdots v_{i_{h+1}}$ runs over all paths of length h in G. A starlike tree is a tree with unique vertex of degree greater than two. Rada and Araujo proved that the starlike trees which have equal connectivity index of order h for all h≥0 are isomorphic. By T(n) we denote the set of the starlike trees on n vertices. In this paper, we characterize the extremal starlike trees with maximum and minimum second order connectivity index in T(n).     

On domination and independent domination numbers of a graph

For a graph G, the definitions of domination number, denoted γ(G), and independent domination number, denoted i(G), are given, and the following results are obtained:Theorem.If G does not have an induced subgraph isomorphic to K_1,3, thenγ(G) = i(G).Corollary 1.For any graph G, γ(L(G))=i(L(G)), where L(G) is the line graph of G. (This extends the result γ(L(T))=i(L(T)), where T is a tree. Hedetniemi and Mitchell, S. E. Conf. Baton Rouge, 1977.)Corollary 2.For any Graph G, γ(M(G))=i(M(G)), where M is the middle graph of G.     

Spanning trees with leaf distance at least four

For a graph G, we denote by i(G) the number of isolated vertices of G. We prove that for a connected graph G of order at least five, if i(G–S) < |S| for all ?? ≠ S ? V(G), then G has a spanning tree T such that the distance in T between any two leaves of T is at least four. This result was conjectured by Kaneko in “Spanning trees with constrains on the leaf degree”, Discrete Applied Math, 115 (2001), 73–76. Moreover, the condition in the result is sharp in a sense that the condition i(G–S) < |S| cannot be replaced by i(G–S) ≤ |S|. © 2006 Wiley Periodicals, Inc. J Graph Theory 55: 83–90, 2007     

Representing edge intersection graphs of paths on degree 4 trees

Let P be a collection of nontrivial simple paths on a host tree T. The edge intersection graph of P, denoted by EPT(P), has vertex set that corresponds to the members of P, and two vertices are joined by an edge if and only if the corresponding members of P share at least one common edge in T. An undirected graph G is called an edge intersection graph of paths in a tree if G=EPT(P) for some P and T. The EPT graphs are useful in network applications. Scheduling undirected calls in a tree network or assigning wavelengths to virtual connections in an optical tree network are equivalent to coloring its EPT graph.An undirected graph G is chordal if every cycle in G of length greater than 3 possesses a chord. Chordal graphs correspond to vertex intersection graphs of subtrees on a tree. An undirected graph G is weakly chordal if every cycle of length greater than 4 in G and in its complement possesses a chord. It is known that the EPT graphs restricted to host trees of vertex degree 3 are precisely the chordal EPT graphs. We prove a new analogous result that weakly chordal EPT graphs are precisely the EPT graphs with host tree restricted to degree 4. Moreover, this provides an algorithm to reduce a given EPT representation of a weakly chordal EPT graph to an EPT representation on a degree 4 tree. Finally, we raise a number of intriguing open questions regarding related families of graphs.     

The clique operator on circular-arc graphs

A circular-arc graphG is the intersection graph of a collection of arcs on the circle and such a collection is called a model of G. Say that the model is proper when no arc of the collection contains another one, it is Helly when the arcs satisfy the Helly Property, while the model is proper Helly when it is simultaneously proper and Helly. A graph admitting a Helly (resp. proper Helly) model is called a Helly (resp. proper Helly) circular-arc graph. The clique graphK(G) of a graph G is the intersection graph of its cliques. The iterated clique graphKⁱ(G) of G is defined by K⁰(G)=G and Kⁱ⁺¹(G)=K(Kⁱ(G)). In this paper, we consider two problems on clique graphs of circular-arc graphs. The first is to characterize clique graphs of Helly circular-arc graphs and proper Helly circular-arc graphs. The second is to characterize the graph to which a general circular-arc graph K-converges, if it is K-convergent. We propose complete solutions to both problems, extending the partial results known so far. The methods lead to linear time recognition algorithms, for both problems.     

On covering vertices of a graph by trees

The purpose of this paper is to initiate study of the following problem: Let G be a graph, and k?1. Determine the minimum number s of trees T₁,…,T_s, Δ(T_i)?k,i=1,…,s, covering all vertices of G. We conjecture: Let G be a connected graph, and k?2. Then the vertices of G can be covered by edge-disjoint trees of maximum degree ?k. As a support for the conjecture we prove the statement for some values of δ and k.     

Extremal problems on detectable colorings of trees

Let G be a connected graph of order 3 or more and let be a coloring of the edges of G (where adjacent edges may be colored the same). For each vertex v of G, the color code of v is the k-tuple c(v)=(a₁,a₂,…,a_k), where a_i is the number of edges incident with v that are colored i (1?i?k). The coloring c is called detectable if distinct vertices have distinct color codes; while the detection number det(G) of G is the minimum positive integer k for which G has a detectable k-coloring. For each integer n?3, let D_T(n) be the maximum detection number among all trees of order n and d_T(n) the minimum detection number among all trees of order n. The numbers D_T(n) and d_T(n) are determined for all integers n?3. Furthermore, it is shown that for integers k?2 and n?3, there exists a tree T of order n having det(T)=k if and only if d_T(n)?k?D_T(n).     

A Euler-Poincaré characteristic for the open set lattices of finite topologies

Let $\text{T}$ be a finite topology. If P and Q are open sets of $\text{T}$ (Q may be the null set) then P is a minimal cover of Q provided Q ? P and there does not exist any open set R of $\text{T}$ such that Q ? R ? P. A subcollection $\text{D}$ of the open sets of $\text{T}$ is termed an i-discrete collection of $\text{T}$ provided $\text{D}$ contains every open O ∈ $\text{T}$ with the property that ? $\text{D}$ ? O ? ? $\text{D}$, $\text{D}$ contains exactly i minimal covers of ? $\text{D}$, and provided ?$\text{D}$ = ?{O | O ∈ $\text{D}$ and O is a minimal cover of ? $\text{D}$}. A single open set is a O-discrete collection. The number of distinct i-discrete collections of $\text{T}$ is denoted by p($\text{T}$, i). If there does not exist any i-discrete collection then p($\text{T}$,i) = 0, and this happens trivially for the case when i is greater than the number of points on which $\text{T}$ is defined. The object of this article is to establish the theorem: For any finite topology $\text{T}$, the quantity E($\text{T}$) = Σ_{i = 0}^∞ (?1)ⁱp($\text{T}$, i) = 1.     

Maximum nullity of outerplanar graphs and the path cover number

Let G=(V,E) be a graph with V={1,2,…,n}. Define S(G) as the set of all n×n real-valued symmetric matrices A=[a_ij] with a_ij≠0,i≠j if and only if ij∈E. By M(G) we denote the largest possible nullity of any matrix A∈S(G). The path cover number of a graph G, denoted P(G), is the minimum number of vertex disjoint paths occurring as induced subgraphs of G which cover all the vertices of G.There has been some success with relating the path cover number of a graph to its maximum nullity. Johnson and Duarte [5], have shown that for a tree T,M(T)=P(T). Barioli et al. [2], show that for a unicyclic graph G,M(G)=P(G) or M(G)=P(G)-1. Notice that both families of graphs are outerplanar. We show that for any outerplanar graph G,M(G)?P(G). Further we show that for any partial 2-path G,M(G)=P(G).     

Radio number for trees

Let G be a connected graph with diameter diam(G). The radio number for G, denoted by rn(G), is the smallest integer k such that there exists a function f:V(G)→{0,1,2,…,k} with the following satisfied for all vertices u and v: |f(u)-f(v)|?diam(G)-d_G(u,v)+1, where d_G(u,v) is the distance between u and v. We prove a lower bound for the radio number of trees, and characterize the trees achieving this bound. Moreover, we prove another lower bound for the radio number of spiders (trees with at most one vertex of degree more than two) and characterize the spiders achieving this bound. Our results generalize the radio number for paths obtained by Liu and Zhu.     

Matchings in starlike trees

Let m(G,k) be the number of k-matchings in the graph G. We write G₁ ⪯ G₂ if m(G₁, k) ≤ m(G₂, k) for all k = 1, 2,…. A tree is said to be starlike if it possesses exactly one vertex of degree greater than two. The relation T₁ ⪯ T₂ is shown to hold for various pairs of starlike trees T₁, T₂. The starlike trees (with a given number of vertices), extremal with respect to the relation ⪯, are characterized.     

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.     

Some tree-star Ramsey Numbers

The Ramsey Number r(G₁, G₂) is the least integer N such that for every graph G with N vertices, either G has the graph G₁ as a subgraph or $\text{G}$, the complement of G, has the graph G₂ as a subgraph.In this paper we embed the paths P_m in a much larger class $\text{T}$ of trees and then show how some evaluations by T. D. Parsons of Ramsey numbers r(P_m, K_1,n), where K_1,n is the star of degree n, are also valid for r(T_m, K_1,n) where T_m ∈ $\text{T}$.     

Balanced decomposition of a vertex-colored graph

A balanced vertex-coloring of a graph G is a function c from V(G) to {−1,0,1} such that ∑{c(v):v∈V(G)}=0. A subset U of V(G) is called a balanced set if U induces a connected subgraph and ∑{c(v):v∈U}=0. A decomposition V(G)=V₁∪?∪V_r is called a balanced decomposition if V_i is a balanced set for 1≤i≤r.In this paper, the balanced decomposition number f(G) of G is introduced; f(G) is the smallest integer s such that for any balanced vertex-coloring c of G, there exists a balanced decomposition V(G)=V₁∪?∪V_r with |V_i|≤s for 1≤i≤r. Balanced decomposition numbers of some basic families of graphs such as complete graphs, trees, complete bipartite graphs, cycles, 2-connected graphs are studied.     

Converse to the Parter-Wiener theorem: The case of non-trees

Through a succession of results, it is known that if the graph of an Hermitian matrix A is a tree and if for some index j, λ∈σ(A)∩σ(A(j)), then there is an index i such that the multiplicity of λ in σ(A(i)) is one more than that in A. We exhibit a converse to this result by showing that it is generally true only for trees. In particular, it is shown that the minimum rank of a positive semidefinite matrix with a given graph G is ?n-2 when G is not a tree. This raises the question of how the minimum rank of a positive semidefinite matrix depends upon the graph in general.     

Graphs with certain families of spanning trees

Sufficient conditions are given in terms of δ(G) and Δ(T), for a graph G with n vertices to contain a tree T with n vertices. One of these sufficient conditions is used to calculate some of the Ramsey numbers for the pair tree-star. Also necessary conditions are given, in terms of δ(G), for a graph G with n vertices to contain all trees with n vertices.     

Permutation-operator inequalities on certain symmetry classes of tensors

If A∈T(m, N), the real-valued N-linear functions on E_m, and σ∈S_N, the symmetric group on {…,N}, then we define the permutation operator P_σ: T(m, N) → T(m, N) such that P_σ(A)(x₁,x₂,…,x_N = A(x_σ(1),x_σ(2),…, x_σ(N)). Suppose Σ^q_i=1n_i = N, where the n_i are positive integers. In this paper we present a condition on σ that is sufficient to guarantee that 〈P_σ(A₁?A₂???A_q),A₁?A₂?? ? A_q〉 ? 0 for A_i∈S(m, n_i), where S(m, n_i) denotes the subspace of T(m, n_i) consisting of all the fully symmetric members of T(m, n_i). Also we present a broad generalization of the Neuberger identity which is sometimes useful in answering questions of the type described below. Suppose G and H are subgroups of S_N. We let T_G(m, N) denote all A∈T(m, N) such that P_σ(A) = A for all σ∈G. We define the symmetrizer $\text{S}$_G: T(m, N)→T_G(m,N) such that $\text{S}{}_{\mathrm{G}}\text{(A) = 1/|G|Σ}{}_{\mathrm{\sigma \in G}}\text{P}{}_{\mathrm{\sigma }}\text{(A)}$. Suppose H is a subgroup of G and A∈T_H(m, N). Clearly $\text{6}\text{S}{}_{\mathrm{<mtext>G</mtext>}}\text{6(A) 6? 6A6.}$ We are interested in the reverse type of comparison. In particular, if D is a suitably chosen subset of T_H(m,N), then can we explicitly present a constant C>0 such that $\text{6}\text{S}{}_{\mathrm{G}}\text{(A)6?C6A6}$ for all A∈D?