Arbitrarily vertex decomposable suns with few rays

A graph G of order n is called arbitrarily vertex decomposable if for each sequence (n₁,…,n_k) of positive integers with n₁+?+n_k=n, there exists a partition (V₁,…,V_k) of the vertex set of G such that V_i induces a connected subgraph of order n_i, for all i=1,…,k. A sun with r rays is a unicyclic graph obtained by adding r hanging edges to r distinct vertices of a cycle. We characterize all arbitrarily vertex decomposable suns with at most three rays. We also provide a list of all on-line arbitrarily vertex decomposable suns with any number of rays.     

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.     

The Harary index of ordinary and generalized quasi-tree graphs

The Harary index is defined as the sum of reciprocals of distances between all pairs of vertices of a connected graph. The quasi-tree graph is a graph G in which there exists a vertex v∈V(G) such that G?v is a tree. In this paper, we presented the upper and lower bounds on the Harary index of all quasi-tree graphs of order n and characterized the corresponding extremal graphs. Moreover we defined the k-generalized quasi-tree graph to be a connected graph G with a subset V _k ?V(G) where |V _k |=k such that G?V _k is a tree. And we also determined the k-generalized quasi-tree graph of order n with maximal Harary index for all values of k and the extremal one with minimal Harary index for k=2.     

On Graphlike k-Dissimilarity Vectors

Let \({\mathcal{G} = (G, w)}\) be a positive-weighted simple finite connected graph, that is, let G be a simple finite connected graph endowed with a function w from the set of edges of G to the set of positive real numbers. For any subgraph \({G^\prime}\) of G, we define \({w(G^\prime)}\) to be the sum of the weights of the edges of \({G^\prime}\) . For any i ₁, . . . , i _k vertices of G, let \({D_{\{i_1,..., i_k\}} (\mathcal{G})}\) be the minimum of the weights of the subgraphs of G connecting i ₁, . . . , i _k . The \({D_{\{i_1,..., i_k\}}(\mathcal{G})}\) are called k-weights of \({\mathcal{G}}\) . Given a family of positive real numbers parametrized by the k-subsets of {1, . . . , n}, \({{\{D_I\}_{I} \in { \{1,...,n\} \choose k}}}\) , we can wonder when there exist a weighted graph \({\mathcal{G}}\) (or a weighted tree) and an n-subset {1, . . . , n} of the set of its vertices such that \({D_I (\mathcal{G}) = D_I}\) for any \({I} \in { \{1,...,n\} \choose k}\) . In this paper we study this problem in the case k =  n?1.     

A degree bound on decomposable trees

A n-vertex graph is said to be decomposable if for any partition (λ₁,…,λ_p) of the integer n, there exists a sequence (V₁,…,V_p) of connected vertex-disjoint subgraphs with |V_i|=λ_i. In this paper, we focus on decomposable trees. We show that a decomposable tree has degree at most 4. Moreover, each degree-4 vertex of a decomposable tree is adjacent to a leaf. This leads to a polynomial time algorithm to decide if a multipode (a tree with only one vertex of degree greater than 2) is decomposable. We also exhibit two families of decomposable trees: arbitrary large trees with one vertex of degree 4, and trees with an arbitrary number of degree-3 vertices.     

Cubicity and Bandwidth

A unit cube in ${\mathbb{R}^k}$ (or a k-cube in short) is defined as the Cartesian product R ₁ × R ₂?× ... × R _k where R _i (for 1??? i??? k) is a closed interval of the form [a _i , a _i + 1] on the real line. A k-cube representation of a graph G is a mapping of the vertices of G to k-cubes such that two vertices in G are adjacent if and only if their corresponding k-cubes have a non-empty intersection. The cubicity of G is the minimum k such that G has a k-cube representation. From a geometric embedding point of view, a k-cube representation of G?=?(V, E) yields an embedding ${f: V(G) \rightarrow \mathbb{R}^k}$ such that for any two vertices u and v, ||f(u) ? f(v)||_?? ?? 1 if and only if ${(u, v) \in E(G)}$ . We first present a randomized algorithm that constructs the cube representation of any graph on n vertices with maximum degree ?? in O(?? ln n) dimensions. This algorithm is then derandomized to obtain a polynomial time deterministic algorithm that also produces the cube representation of the input graph in the same number of dimensions. The bandwidth ordering of the graph is studied next and it is shown that our algorithm can be improved to produce a cube representation of the input graph G in O(?? ln b) dimensions, where b is the bandwidth of G, given a bandwidth ordering of G. Note that b ?? n and b is much smaller than n for many well-known graph classes. Another upper bound of b + 1 on the cubicity of any graph with bandwidth b is also shown. Together, these results imply that for any graph G with maximum degree ?? and bandwidth b, the cubicity is O(min{b, ?? ln b}). The upper bound of b?+ 1 is used to derive upper bounds for the cubicity of circular-arc graphs, cocomparability graphs and AT-free graphs in terms of the maximum degree ??.     

Resolvability in circulant graphs

A set W of the vertices of a connected graph G is called a resolving set for G if for every two distinct vertices u, v ∈ V (G) there is a vertex w ∈ W such that d(u, w) ≠ d(v, w). A resolving set of minimum cardinality is called a metric basis for G and the number of vertices in a metric basis is called the metric dimension of G, denoted by dim(G). For a vertex u of G and a subset S of V (G), the distance between u and S is the number min s∈S d(u, s). A k-partition Π = {S 1 , S 2 , . . . , S k } of V (G) is called a resolving partition if for every two distinct vertices u, v ∈ V (G) there is a set S i in Π such that d(u, Si )≠ d(v, Si ). The minimum k for which there is a resolving k-partition of V (G) is called the partition dimension of G, denoted by pd(G). The circulant graph is a graph with vertex set Zn , an additive group of integers modulo n, and two vertices labeled i and j adjacent if and only if i-j (mod n) ∈ C , where CZn has the property that C =-C and 0 ■ C. The circulant graph is denoted by Xn, Δ where Δ = |C|. In this paper, we study the metric dimension of a family of circulant graphs Xn, 3 with connection set C = {1, n/2 , n-1} and prove that dim(Xn, 3 ) is independent of choice of n by showing that dim(Xn, 3 ) ={3 for all n ≡ 0 (mod 4), 4 for all n ≡ 2 (mod 4). We also study the partition dimension of a family of circulant graphs Xn,4 with connection set C = {±1, ±2} and prove that pd(Xn, 4 ) is independent of choice of n and show that pd(X5,4 ) = 5 and pd(Xn,4 ) ={3 for all odd n ≥ 9, 4 for all even n ≥ 6 and n = 7.     

On the shape of decomposable trees

A n-vertex graph is said to be decomposable if, for any partition (λ₁,…,λ_p) of the integer n, there exists a sequence (V₁,…,V_p) of connected vertex-disjoint subgraphs with |V_i|=λ_i. The aim of the paper is to study the homeomorphism classes of decomposable trees. More precisely, we show that homeomorphism classes containing decomposable trees with an arbitrarily large minimal distance between all pairs of distinct vertices of degree different from 2, is exactly the set of combs.     

Pancyclicity of connected circulant graphs

The circulant G_n(a₁, ⋖, a_k), where 0 < a₁ < ··· < a_k < (n + 1)/2, is defined as the vertex-transitive graph that has vertices i ± a₁, ···, i ± a_k(mod n) adjacent to each vertex i. In this work we show that the connected circulants of degree at least three contain all even cycles. In addition, we prove that the connected circulants of girth three contain cycles of all lengths. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 17–25, 1997     

Connected graphs with maximal Q-index: The one-dominating-vertex case

By the signless Laplacian of a (simple) graph G we mean the matrix Q(G)=D(G)+A(G), where A(G),D(G) denote respectively the adjacency matrix and the diagonal matrix of vertex degrees of G. For every pair of positive integers n,k, it is proved that if 3?k?n-3, then H_n,k, the graph obtained from the star K_1,n-1 by joining a vertex of degree 1 to k+1 other vertices of degree 1, is the unique connected graph that maximizes the largest signless Laplacian eigenvalue over all connected graphs with n vertices and n+k edges.     

Spanning Trees with a Bounded Number of Branch Vertices in a Claw-Free Graph

Let k be a non-negative integer. A branch vertex of a tree is a vertex of degree at least three. We show two sufficient conditions for a connected claw-free graph to have a spanning tree with a bounded number of branch vertices: (i) A connected claw-free graph has a spanning tree with at most k branch vertices if its independence number is at most 2k + 2. (ii) A connected claw-free graph of order n has a spanning tree with at most one branch vertex if the degree sum of any five independent vertices is at least n ? 2. These conditions are best possible. A related conjecture also is proposed.     

A New Construction for Cohen–Macaulay Graphs

Let G be a finite simple graph on a vertex set V(G) = {x ₁₁,…, x _n1}. Also let m ₁,…, m _n  ≥ 2 be integers and G ₁,…, G _n be connected simple graphs on the vertex sets V(G _i ) = {x _i1,…, x _{im i} }. In this article, we provide necessary and sufficient conditions on G ₁,…, G _n for which the graph obtained by attaching the G _i to G is unmixed or vertex decomposable. Then we characterize Cohen–Macaulay and sequentially Cohen–Macaulay graphs obtained by attaching the cycle graphs or connected chordal graphs to arbitrary graphs.     

A note on on-line ranking number of graphs

A k-ranking of a graph G = (V, E) is a mapping ϕ: V → {1, 2, ..., k} such that each path with end vertices of the same colour c contains an internal vertex with colour greater than c. The ranking number of a graph G is the smallest positive integer k admitting a k-ranking of G. In the on-line version of the problem, the vertices v ₁, v ², ..., v _n of G arrive one by one in an arbitrary order, and only the edges of the induced graph G[{v ₁, v ₂, ..., v _i }] are known when the colour for the vertex v _i has to be chosen. The on-line ranking number of a graph G is the smallest positive integer k such that there exists an algorithm that produces a k-ranking of G for an arbitrary input sequence of its vertices. We show that there are graphs with arbitrarily large difference and arbitrarily large ratio between the ranking number and the on-line ranking number. We also determine the on-line ranking number of complete n-partite graphs. The question of additivity and heredity is discussed as well.     

Characterizing defect n-extendable graphs and -critical graphs

A near perfect matching is a matching saturating all but one vertex in a graph. Let G be a connected graph. If any n independent edges in G are contained in a near perfect matching where n is a positive integer and n(|V(G)|-2)/2, then G is said to be defect n-extendable. If deleting any k vertices in G where k|V(G)|-2, the remaining graph has a perfect matching, then G is a k-critical graph. This paper first shows that the connectivity of defect n-extendable graphs can be any integer. Then the characterizations of defect n-extendable graphs and (2k+1)-critical graphs using M-alternating paths are presented.     

Note on group distance magic complete bipartite graphs

A Γ-distance magic labeling of a graph G = (V, E) with |V| = n is a bijection ? from V to an Abelian group Γ of order n such that the weight $w(x) = \sum\nolimits_{y \in N_G (x)} {\ell (y)}$ of every vertex x ∈ V is equal to the same element µ ∈ Γ, called the magic constant. A graph G is called a group distance magic graph if there exists a Γ-distance magic labeling for every Abelian group Γ of order |V(G)|. In this paper we give necessary and sufficient conditions for complete k-partite graphs of odd order p to be ? _p -distance magic. Moreover we show that if p ≡ 2 (mod 4) and k is even, then there does not exist a group Γ of order p such that there exists a Γ-distance labeling for a k-partite complete graph of order p. We also prove that K _m,n is a group distance magic graph if and only if n + m ? 2 (mod 4).     

Connected Resolvability of Graphs

For an ordered set W = {w ₁, w ₂,..., w _k} of vertices and a vertex v in a connected graph G, the representation of v with respect to W is the k-vector r(v|W) = (d(v, w ₁), d(v, w ₂),... d(v, w _k)), where d(x, y) represents the distance between the vertices x and y. The set W is a resolving set for G if distinct vertices of G have distinct representations with respect to W. A resolving set for G containing a minimum number of vertices is a basis for G. The dimension dim(G) is the number of vertices in a basis for G. A resolving set W of G is connected if the subgraph 〈W〉 induced by W is a nontrivial connected subgraph of G. The minimum cardinality of a connected resolving set in a graph G is its connected resolving number cr(G). Thus 1 ≤ dim(G) ≤ cr(G) ≤ n?1 for every connected graph G of order n ≥ 3. The connected resolving numbers of some well-known graphs are determined. It is shown that if G is a connected graph of order n ≥ 3, then cr(G) = n?1 if and only if G = K _n or G = K _1,n?1. It is also shown that for positive integers a, b with a ≤ b, there exists a connected graph G with dim(G) = a and cr(G) = b if and only if $\left( {a,b} \right) \notin \left\{ {\left( {1,k} \right):k = 1\;{\text{or}}\;k \geqslant 3} \right\}$ Several other realization results are present. The connected resolving numbers of the Cartesian products G × K ₂ for connected graphs G are studied.     

Small cycles and 2-factor passing through any given vertices in graphs

The theory of vertex-disjoint cycles and 2-factor of graphs has important applications in computer science and network communication. For a graph G, let σ ₂(G):=min?{d(u)+d(v)|uv ? E(G),u≠v}. In the paper, the main results of this paper are as follows:

1. Let k≥2 be an integer and G be a graph of order n≥3k, if σ ₂(G)≥n+2k?2, then for any set of k distinct vertices v ₁,…,v _k , G has k vertex-disjoint cycles C ₁,C ₂,…,C _k of length at most four such that v _i ∈V(C _i ) for all 1≤i≤k.
2. Let k≥1 be an integer and G be a graph of order n≥3k, if σ ₂(G)≥n+2k?2, then for any set of k distinct vertices v ₁,…,v _k , G has k vertex-disjoint cycles C ₁,C ₂,…,C _k such that:
   1. v _i ∈V(C _i ) for all 1≤i≤k.
   2. V(C ₁)∪???∪V(C _k )=V(G), and
   3. |C _i |≤4, 1≤i≤k?1.

Moreover, the condition on σ ₂(G)≥n+2k?2 is sharp.     

Connected Baranyai’s theorem

Let K _n ^h = (V, ( _h ^V )) be the complete h-uniform hypergraph on vertex set V with ¦V¦ = n. Baranyai showed that K _n ^h can be expressed as the union of edge-disjoint r-regular factors if and only if h divides rn and r divides \((_{h - 1}^{n - 1} )\) . Using a new proof technique, in this paper we prove that λK _n ^h can be expressed as the union \(\mathcal{G}_1 \cup ... \cup \mathcal{G}_k \) of k edge-disjoint factors, where for 1≤i≤k, \(\mathcal{G}_i \) is r _i -regular, if and only if (i) h divides r _i n for 1≤i≤k, and (ii) \(\sum\nolimits_{i = 1}^k {r_i = \lambda (_{h - 1}^{n - 1} )} \) . Moreover, for any i (1≤i≤k) for which r _i ≥2, this new technique allows us to guarantee that \(\mathcal{G}_i \) is connected, generalizing Baranyai’s theorem, and answering a question by Katona.     

Partitions of a graph into paths with prescribed endvertices and lengths

For a graph G, let σ₂(G) denote the minimum degree sum of a pair of nonadjacent vertices. We conjecture that if |V(G)| = n = Σ^k_{i = 1} a_i and σ₂(G) ≥ n + k − 1, then for any k vertices v₁, v₂,…, v_k in G, there exist vertex‐disjoint paths P₁, P₂,…, P_k such that |V(P_i)| = a_i and v_i is an endvertex of P_i for 1 ≤ i ≤ k. In this paper, we verify the conjecture for the cases where almost all a_i ≤ 5, and the cases where k ≤ 3. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 163–169, 2000     

A relationship between bounds on the sum of squares of degrees of a graph

LetG = (V, E) be a simple graph withn vertices and e edges. Letdi be the degree of the ith vertex v_i ∈ V andm _i the average of the degrees of the vertices adjacent to vertexv _i ∈ V. It is known by Caen [1] and Das [2] that $\frac{{4e^2 }}{n} \leqslant d_1^2 + ... + d_n^2 \leqslant e max \{ d_j + m_j |v_j \in V\} \leqslant e\left( {\frac{{2e}}{{n - 1}} + n - 2} \right)$ . In general, the equalities do not hold in above inequality. It is shown that a graphG is regular if and only if $\frac{{4e^2 }}{n} = d_1^2 + ... + d_n^2 $ . In fact, it is shown a little bit more strong result that a graphG is regular if and only if $\frac{{4e^2 }}{n} = d_1^2 + ... + d_n^2 = e max \{ d_j + m_j |v_j \in V\} $ . For a graphG withn < 2 vertices, it is shown that G is a complete graphK _n if and only if $\frac{{4e^2 }}{n} = d_1^2 + ... + d_n^2 = e max \{ d_j + m_j |v_j \in V\} = e\left( {\frac{{2e}}{{n - 1}} + n - 2} \right)$ .