The $$(k,\ell )$$ ( k, ℓ ) -proper index of graphs

Hong Chang (), Xueliang Li (), Colton Magnant () and Zhongmei Qin ()
Additional contact information
Hong Chang: Nankai University
Xueliang Li: Nankai University
Colton Magnant: Georgia Southern University
Zhongmei Qin: Nankai University

Journal of Combinatorial Optimization, 2018, vol. 36, issue 2, No 8, 458-471

Abstract: Abstract A tree T in an edge-colored graph is called a proper tree if no two adjacent edges of T receive the same color. Let G be a connected graph of order n and k be an integer with $$2\le k \le n$$ 2 ≤ k ≤ n . For $$S\subseteq V(G)$$ S ⊆ V ( G ) and $$|S| \ge 2$$ | S | ≥ 2 , an S-tree is a tree containing the vertices of S in G. A set $$\{T_1,T_2,\ldots ,T_\ell \}$$ { T 1 , T 2 , … , T ℓ } of S-trees is called internally disjoint if $$E(T_i)\cap E(T_j)=\emptyset $$ E ( T i ) ∩ E ( T j ) = ∅ and $$V(T_i)\cap V(T_j)=S$$ V ( T i ) ∩ V ( T j ) = S for $$1\le i\ne j\le \ell $$ 1 ≤ i ≠ j ≤ ℓ . For a set S of k vertices of G, the maximum number of internally disjoint S-trees in G is denoted by $$\kappa (S)$$ κ ( S ) . The k-connectivity $$\kappa _k(G)$$ κ k ( G ) of G is defined by $$\kappa _k(G)=\min \{\kappa (S)\mid S$$ κ k ( G ) = min { κ ( S ) ∣ S is a k-subset of $$V(G)\}$$ V ( G ) } . For a connected graph G of order n and for two integers k and $$\ell $$ ℓ with $$2\le k\le n$$ 2 ≤ k ≤ n and $$1\le \ell \le \kappa _k(G)$$ 1 ≤ ℓ ≤ κ k ( G ) , the $$(k,\ell )$$ ( k , ℓ ) -proper index $$px_{k,\ell }(G)$$ p x k , ℓ ( G ) of G is the minimum number of colors that are required in an edge-coloring of G such that for every k-subset S of V(G), there exist $$\ell $$ ℓ internally disjoint proper S-trees connecting them. In this paper, we show that for every pair of positive integers k and $$\ell $$ ℓ with $$k \ge 3$$ k ≥ 3 and $$\ell \le \kappa _k(K_{n,n})$$ ℓ ≤ κ k ( K n , n ) , there exists a positive integer $$N_1=N_1(k,\ell )$$ N 1 = N 1 ( k , ℓ ) such that $$px_{k,\ell }(K_n) = 2$$ p x k , ℓ ( K n ) = 2 for every integer $$n \ge N_1$$ n ≥ N 1 , and there exists also a positive integer $$N_2=N_2(k,\ell )$$ N 2 = N 2 ( k , ℓ ) such that $$px_{k,\ell }(K_{m,n}) = 2$$ p x k , ℓ ( K m , n ) = 2 for every integer $$n \ge N_2$$ n ≥ N 2 and $$m=O(n^r) (r \ge 1)$$ m = O ( n r ) ( r ≥ 1 ) . In addition, we show that for every $$p \ge c\root k \of {\frac{\log _a n}{n}}$$ p ≥ c log a n n k ( $$c \ge 5$$ c ≥ 5 ), $$px_{k,\ell }(G_{n,p})\le 2$$ p x k , ℓ ( G n , p ) ≤ 2 holds almost surely, where $$G_{n,p}$$ G n , p is the Erdős–Rényi random graph model.

Keywords: Proper tree; Proper index; Random graphs; Threshold function; 05C15; 05C40; 05C80; 05D40 (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-018-0307-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:36:y:2018:i:2:d:10.1007_s10878-018-0307-5

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-018-0307-5

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().