Zum Inhalt

Erweiterte Suche

Ergebnisvorschau für Ihre aktuellen Suchbegriffe: 0

Suchoperatoren:

Sie können Operatoren mit Ihrer Suchanfrage kombinieren, um diese noch präziser einzugrenzen. Klicken Sie auf den Suchoperator, um eine Erklärung seiner Funktionsweise anzuzeigen.
Findet Dokumente mit genau dieser Wortgruppe in exakt dieser Schreibweise und Reihenfolge (z.B. "employer branding").
Findet Dokumente, in denen beide Begriffe zusammen vorkommen (z.B. vertrieb UND bonus).
Findet Dokumente, in denen einer der beiden oder beide Begriffe vorkommen (z.B. porsche OR volkswagen).
Findet Dokumente, in denen alle Begriffe vorkommen. Das Leerzeichen wird als UND interpretiert (z.B. mensch roboter alltag).
Findet Dokumente, in denen der Begriff nach NOT nicht vorkommt (z.B. ford NOT "harrison ford").
Findet Dokumente, in denen der gesuchte Begriff mehr als n mal vorkommt. n steht für eine beliebige Anzahl (z.B. COUNT(getriebe)>8).
Findet Dokumente, in denen beide Begriffe in beliebiger Reihenfolge innerhalb von maximal n Worten zueinander stehen. Empfehlung: Wählen Sie zwischen 15 und 30 als maximale Wortanzahl (z.B. NEAR(hybrid, antrieb, 20)).
Findet Dokumente, in denen der Begriff in Wortvarianten vorkommt, wobei diese VOR, HINTER oder VOR und HINTER dem Suchbegriff anschließen können (z.B., leichtbau*, *leichtbau, *leichtbau*).
Findet Dokumente mit dem Suchbegriff in verschiedenen Schreibweisen. Das ? steht für eine einzige Stelle (z.B. organi?ation).
Sonderzeichen werden als UND interpretiert (z.B. Mann + Hummel).

Semantische Suche

powered by (Link öffnet in neuem Fenster)
loading …
Anmelden
Nach oben

Properly Colored Connectivity of Graphs

  • 2018
  • Buch
Verfasst von
Xueliang Li
Colton Magnant
Zhongmei Qin
Buchreihe
SpringerBriefs in Mathematics
Verlag
Springer International Publishing
Enthalten in
Springer Professional "Wirtschaft+Technik"
Springer Professional "Technik"
Springer Professional "Wirtschaft"
insite
SUCHEN

Über dieses Buch

A comprehensive survey of proper connection of graphs is discussed in this book with real world applications in computer science and network security. Beginning with a brief introduction, comprising relevant definitions and preliminary results, this book moves on to consider a variety of properties of graphs that imply bounds on the proper connection number. Detailed proofs of significant advancements toward open problems and conjectures are presented with complete references.

Researchers and graduate students with an interest in graph connectivity and colorings will find this book useful as it builds upon fundamental definitions towards modern innovations, strategies, and techniques. The detailed presentation lends to use as an introduction to proper connection of graphs for new and advanced researchers, a solid book for a graduate level topics course, or as a reference for those interested in expanding and further developing research in the area.

Inhaltsverzeichnis

Frontmatter
Chapter 1. Introduction
Abstract
Graph connectivity has been studied from a variety of perspectives in applications and theoretical endeavors. In this text, we consider properly colored connectivity of graphs, which are motivated by network connectivity and security applications as well as related theoretical notions.
Xueliang Li, Colton Magnant, Zhongmei Qin
Chapter 2. General Results
Abstract
In this chapter, we state some general results for proper connection number of graphs. There is an easy lower bound on pc(G) using the maximum number of bridges (cut edges) incident to a single vertex. All such bridges must receive distinct colors for the coloring to be proper connected, so the following result comes at no surprise.
Xueliang Li, Colton Magnant, Zhongmei Qin
Chapter 3. Connectivity Conditions
Abstract
In this chapter, we provide several results concerning the proper connection number using connectivity to measure the number of edges and their distribution.
Xueliang Li, Colton Magnant, Zhongmei Qin
Chapter 4. Degree Conditions
Abstract
In this chapter, we consider results which use assumptions on the degrees or number of edges, thereby driving the proper connection number down.
Xueliang Li, Colton Magnant, Zhongmei Qin
Chapter 5. Domination Conditions
Abstract
Relating the proper connection number with domination, the following results were proven in Li et al. (Theor Comput Sci 607:480–487, 2015). A dominating set for a graph G = (V, E) is a subset D of V such that every vertex not in D is adjacent to at least one member of D. A dominating set D is called two-way two-step dominating if every pendant vertex is included in D and every vertex at distance at least 2 from D has at least two neighbors at distance 1 from D.
Xueliang Li, Colton Magnant, Zhongmei Qin
Chapter 6. Operations on Graphs
Abstract
Among the many interesting problems of determining the proper connection numbers of graphs, it is worthwhile to study the proper connection number of G according to some constraints of the complementary graph.
Xueliang Li, Colton Magnant, Zhongmei Qin
Chapter 7. Random Graphs
Abstract
For random graphs, the following results were shown in Gu et al. (Theor Comput Sci 609:336–343, 2016). Here let G(n, p) denote the Erdős-Renyi (Erdős and Rényi, Magy Tud Akad Mat Kutató Int Közl 5:17–61, 1960) random graph with n vertices and edges appearing with probability p. We say an event \(\mathcal {A}\) happens with high probability if the probability that it happens approaches 1 as n →∞, i.e., \(Pr[\mathcal {A}]=1-o_n(1)\). Sometimes, we say w.h.p. for short. We say that a property holds for almost all graphs if the probability of the property holding for G(n, 1∕2) approaches 1 as n approaches infinity. The first result follows easily from Theorem 3.​0.​2 and the fact that almost all graphs are 3-connected (Blass and Harary, J Graph Theory 3:225–240, 1979).
Xueliang Li, Colton Magnant, Zhongmei Qin
Chapter 8. Proper k-Connection and Strong Proper Connection
Abstract
Using a minimum degree assumption to provide density, the following was shown for pc 2(G). The proper 2-connection number pc 2(G) is the minimum number of colors needed to color the edges of G so that between every pair of vertices, there are at least two internally disjoint proper paths. First we present an easy lemma without proof.
Xueliang Li, Colton Magnant, Zhongmei Qin
Chapter 9. Proper Vertex Connection and Total Proper Connection
Abstract
Notions of vertex proper connection, the vertex-coloring version of the proper connection number, have been defined and studied independently in Chizmar et al. (AKCE Int J Graphs Comb 13(2):103–106, 2016) and Jiang et al. (Bull Malays Math Sci Soc 41(1):415–425, 2018). A vertex-colored graph G is called proper vertex k-connected if every pair of vertices is connected by k internally disjoint paths, each of which has no two consecutive internal vertices of the same color. Define the proper vertex k-connection number of G, denoted by pvc k (G), to be the smallest number of (vertex) colors needed to make G proper vertex k-connected. We write pvc(G) for pvc 1(G). Here the end vertices are not included to be consistent with the similarly defined rainbow vertex connection number where, if end vertices were included, all vertices would necessarily receive distinct colors.
Xueliang Li, Colton Magnant, Zhongmei Qin
Chapter 10. Directed Graphs
Abstract
Much like the undirected version, a strongly connected directed graph is called proper connected if between every ordered pair of vertices, there is a directed properly colored path. Defined in Magnant et al. (Matematiqki Vesnik 68(1):58–65, 2016), the directed proper connection number of a strongly connected directed graph G, denoted by \(\overrightarrow {pc}(G)\), is the minimum number of colors needed to color the (directed) edges so that the directed graph is proper connected. Clearly \(\overrightarrow {pc}(G) \geq 2\) for any G since a directed edge from u to v implies there is no directed edge from v to u so a directed path from v to u must use at least 2 colors.
Xueliang Li, Colton Magnant, Zhongmei Qin
Chapter 11. Other Generalizations
Abstract
There have been several generalizations or extensions of the proper connection number. We discuss a few of these in this chapter.
Xueliang Li, Colton Magnant, Zhongmei Qin
Chapter 12. Computational Complexity
Abstract
First of all, we introduce some basis notions about computational complexity.
Xueliang Li, Colton Magnant, Zhongmei Qin
Backmatter
Titel
Properly Colored Connectivity of Graphs
Verfasst von
Xueliang Li
Colton Magnant
Zhongmei Qin
Copyright-Jahr
2018
Electronic ISBN
978-3-319-89617-5
Print ISBN
978-3-319-89616-8
DOI
https://doi.org/10.1007/978-3-319-89617-5

Informationen zur Barrierefreiheit für dieses Buch folgen in Kürze. Wir arbeiten daran, sie so schnell wie möglich verfügbar zu machen. Vielen Dank für Ihre Geduld.

Premium Partner

    Bildnachweise
    AvePoint Deutschland GmbH/© AvePoint Deutschland GmbH, NTT Data/© NTT Data, Wildix/© Wildix, arvato Systems GmbH/© arvato Systems GmbH, Ninox Software GmbH/© Ninox Software GmbH, Nagarro GmbH/© Nagarro GmbH, GWS mbH/© GWS mbH, CELONIS Labs GmbH, USU GmbH/© USU GmbH, G Data CyberDefense/© G Data CyberDefense, Vendosoft/© Vendosoft, Kumavision/© Kumavision, Noriis Network AG/© Noriis Network AG, WSW Software GmbH/© WSW Software GmbH, tts GmbH/© tts GmbH, Asseco Solutions AG/© Asseco Solutions AG, AFB Gemeinnützige GmbH/© AFB Gemeinnützige GmbH, Ferrari electronic AG/© Ferrari electronic AG