scroll identifier for mobile
main-content

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

17.05.2018 | Ausgabe 2/2018

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

Zeitschrift:
Journal of Combinatorial Optimization > Ausgabe 2/2018
Autoren:
Hong Chang, Xueliang Li, Colton Magnant, Zhongmei Qin
Wichtige Hinweise
Supported by NSFC No. 11531011.

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$$. For $$S\subseteq V(G)$$ and $$|S| \ge 2$$, an S-tree is a tree containing the vertices of S in G. A set $$\{T_1,T_2,\ldots ,T_\ell \}$$ of S-trees is called internally disjoint if $$E(T_i)\cap E(T_j)=\emptyset$$ and $$V(T_i)\cap V(T_j)=S$$ for $$1\le i\ne j\le \ell$$. For a set S of k vertices of G, the maximum number of internally disjoint S-trees in G is denoted by $$\kappa (S)$$. The k-connectivity $$\kappa _k(G)$$ of G is defined by $$\kappa _k(G)=\min \{\kappa (S)\mid S$$ is a k-subset of $$V(G)\}$$. For a connected graph G of order n and for two integers k and $$\ell$$ with $$2\le k\le n$$ and $$1\le \ell \le \kappa _k(G)$$, the $$(k,\ell )$$-proper index $$px_{k,\ell }(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$$ and $$\ell \le \kappa _k(K_{n,n})$$, there exists a positive integer $$N_1=N_1(k,\ell )$$ such that $$px_{k,\ell }(K_n) = 2$$ for every integer $$n \ge N_1$$, and there exists also a positive integer $$N_2=N_2(k,\ell )$$ such that $$px_{k,\ell }(K_{m,n}) = 2$$ for every integer $$n \ge N_2$$ and $$m=O(n^r) (r \ge 1)$$. In addition, we show that for every $$p \ge c\root k \of {\frac{\log _a n}{n}}$$ ($$c \ge 5$$), $$px_{k,\ell }(G_{n,p})\le 2$$ holds almost surely, where $$G_{n,p}$$ is the Erdős–Rényi random graph model.

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

• über 69.000 Bücher
• über 500 Zeitschriften

aus folgenden Fachgebieten:

• Automobil + Motoren
• Bauwesen + Immobilien
• Elektrotechnik + Elektronik
• Energie + Umwelt
• Finance + Banking
• Management + Führung
• Marketing + Vertrieb
• Maschinenbau + Werkstoffe

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

• über 58.000 Bücher
• über 300 Zeitschriften

aus folgenden Fachgebieten:

• Bauwesen + Immobilien
• Finance + Banking
• Management + Führung
• Marketing + Vertrieb

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

• über 50.000 Bücher
• über 380 Zeitschriften

aus folgenden Fachgebieten:

• Automobil + Motoren
• Bauwesen + Immobilien
• Elektrotechnik + Elektronik
• Energie + Umwelt
• Maschinenbau + Werkstoffe​​​​​​​​​​​​​​

Testen Sie jetzt 30 Tage kostenlos.

Literatur
Über diesen Artikel

Zur Ausgabe

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.

Whitepaper

- ANZEIGE -

Best Practices für die Mitarbeiter-Partizipation in der Produktentwicklung

Unternehmen haben das Innovationspotenzial der eigenen Mitarbeiter auch außerhalb der F&E-Abteilung erkannt. Viele Initiativen zur Partizipation scheitern in der Praxis jedoch häufig. Lesen Sie hier  - basierend auf einer qualitativ-explorativen Expertenstudie - mehr über die wesentlichen Problemfelder der mitarbeiterzentrierten Produktentwicklung und profitieren Sie von konkreten Handlungsempfehlungen aus der Praxis.