Home About us Contact
|
Home About us Contact | ||
|
|
||
K Vertices (k + vertex)
Selected AbstractsProof of a tiling conjecture of KomlósRANDOM STRUCTURES AND ALGORITHMS, Issue 2 2003Ali Shokoufandeh Abstract A conjecture of Komlós states that for every graph H, there is a constant K such that if G is any n -vertex graph of minimum degree at least (1 , (1/,cr(H)))n, where ,cr(H) denotes the critical chromatic number of H, then G contains an H -matching that covers all but at most K vertices of G. In this paper we prove that the conjecture holds for all sufficiently large values of n. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 180,205, 2003 [source] The kth Laplacian eigenvalue of a treeJOURNAL OF GRAPH THEORY, Issue 1 2007Ji-Ming Guo Abstract Let ,k(G) be the kth Laplacian eigenvalue of a graph G. It is shown that a tree T with n vertices has and that equality holds if and only if k < n, k|n and T is spanned by k vertex disjoint copies of , the star on vertices. © 2006 Wiley Periodicals, Inc. J Graph Theory [source] Rainbow trees in graphs and generalized connectivityNETWORKS: AN INTERNATIONAL JOURNAL, Issue 4 2010Gary Chartrand Abstract An edge-colored tree T is a rainbow tree if no two edges of T are assigned the same color. Let G be a nontrivial connected graph of order n and let k be an integer with 2 , k , n. A k -rainbow coloring of G is an edge coloring of G having the property that for every set S of k vertices of G, there exists a rainbow tree T in G such that S , V(T). The minimum number of colors needed in a k -rainbow coloring of G is the k -rainbow index of G. For every two integers k and n , 3 with 3 , k , n, the k -rainbow index of a unicyclic graph of order n is determined. For a set S of vertices in a connected graph G of order n, a collection {T1,T2,,,T,} of trees in G is said to be internally disjoint connecting S if these trees are pairwise edge-disjoint and V(Ti) , V(Tj) = S for every pair i,j of distinct integers with 1 , i,j , ,. For an integer k with 2 , k , n, the k -connectivity ,k(G) of G is the greatest positive integer , for which G contains at least , internally disjoint trees connecting S for every set S of k vertices of G. It is shown that ,k(Kn)=n,,k/2, for every pair k,n of integers with 2 , k , n. For a nontrivial connected graph G of order n and for integers k and , with 2 , k , n and 1 , , , ,k(G), the (k,,)-rainbow index rxk,,(G) of G is the minimum number of colors needed in an edge coloring of G such that G contains at least , internally disjoint rainbow trees connecting S for every set S of k vertices of G. The numbers rxk,,(Kn) are determined for all possible values k and , when n , 6. It is also shown that for , , {1, 2}, rx3,,(Kn) = 3 for all n , 6. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010 [source] Multiterminal resilience for series-parallel networksNETWORKS: AN INTERNATIONAL JOURNAL, Issue 2 2007Toni R. Farley Abstract Network resilience measures the average two-terminal reliability (connectedness) of a network. Multiterminal resilience extends this measure to any k vertices; it is the average k -terminal reliability of a network. This generalizes two well-studied network connectedness measures. Calculating multiterminal resilience on general networks encompasses all-terminal reliability and thus is NP-hard. Multiterminal resilience is examined on undirected series-parallel networks, and an efficient (polynomial time) algorithm is developed for calculating the resilience for every k. Applications in mobile ad hoc and sensor networks are outlined. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(2), 164,172 2007 [source] | ||||||||||