Search

When the vertices and edges are colored with k colors, an edge is called monochromatic if the edge and the two vertices incident with it all have the same color. The adapted chromatic number of a graph G, $$\chi _{a}\left( G\right) ,$$ is the least integer k such that for each k-edge coloring of G the vertices of G can be colored with the same set of colors without creating any monochromatic edges. It is easy to see that $$\chi _{a}\left( G\right) \le \chi \left( G\right) $$ . While this bound is tight, all the known graphs attaining this bound are not color critical. It is known that if G is a critical graph, then $$\chi _{a}\left( G\right) \le \chi \left( G\right) -1$$ . In this article we construct a family of k-critical graphs whose adapted chromatic number is exactly one less than their chromatic number. This answers a question in Molloy and Thron (J Graph Theory 71:331–351, 2012). We also study the properties of graphs that are critical with respect to adaptable chromatic number.

Graph grammars may be used to formally describe computational systems, modeling the states as graphs and the possible state changes as rules (whose left- and right-hand sides are graphs). The behavior of the system is defined by the application of these rules to the state-graphs. From a practical point of view, the extension of rules to enable description of extra conditions that must be satisfied upon rule application is highly desirable. An example is the specification of negative application conditions, or NACs, that describe situations that prevent the application of a rule. This extension of the basic formalism enhances the expressiveness of rules, generally allowing simpler specifications. Another extension that is fundamental for practical applications is the possibility to use data types, like natural numbers, lists, etc., as attributes of graphical elements (vertices and edges). Attributed graph grammars are well-investigated and used. However, there is a lack of verification techniques for this kind of grammar mainly due to the fact that data types are typically infinite domains, and thus techniques like model checking can not be used directly (without abstraction constructions). The present work provides a theoretical foundation for theorem proving graph grammars with negative application conditions and attributes. This is achieved by generating an event-B model from a graph grammar. Event-B models are composed by sets and axioms to define types, and by states and events to describe behavior. After constructing the event-B model that is semantically equivalent to a graph grammar, properties about reachable states may be proven using the various theorem provers available for event-B in the Rodin platform. This strategy allows the verification of systems with infinite-state spaces without using any kind of approximation.

In recent years there has been much progress in graph theory on questions of the following type. What is the threshold for a certain large substructure to appear in a random graph? When does a random graph contain all structures from a given family? And when does it contain them so robustly that even an adversary who is allowed to perturb the graph cannot destroy all of them? I will survey this progress, and highlight the vital role played by some newly developed methods, such as the sparse regularity method, the absorbing method, and the container method. I will also mention many open questions that remain in this area.

We discuss the problem of finding critical sets in graphs, a concept which has appeared in a number of guises in the combinatorics and graph theory literature. The case of the Sudoku graph receives particular attention, because critical sets correspond to minimal fair puzzles. We define four parameters associated with the sizes of extremal critical sets and (a) prove several general results concerning the properties of these parameters, including their computational intractability, (b) compute their values exactly for some classes of graphs, (c) obtain bounds for generalized Sudoku graphs, and (d) offer a number of open questions regarding critical sets and the aforementioned parameters.

With the increasingly development of system complexity, there is a variety of indeterminacy in the practical applications of graph theory. In this paper, the uncertainty theory is applied to study the regularity of the uncertain graph. Based on the uncertainty theory, the concept of regularity index of uncertain graph and its calculation method are raised with an illustration of the calculation method as the final part in the paper.

In practical applications of graph theory, non-deterministic factors are frequently encountered. This paper employs uncertainty theory to deal with non-deterministic factors in problems of graph connectivity. The concepts of uncertain graph and connectedness index of uncertain graph are proposed in this paper. It presents two algorithms to calculate connectedness index of an uncertain graph.

We study extremal graphs for the extremal values of the second largest Q-eigenvalue of a connected graph. We first characterize all simple connected graphs with second largest signless Laplacian eigenvalue at most 3. The second part of the present paper is devoted to the study of the graphs that maximize the second largest Q-eigenvalue. We construct families of such graphs and prove that some of theses families are minimal for the fact that they maximize the second largest signless Laplacian eigenvalue.

Uncertain graphs are prevalent in several applications including communications systems, biological databases, and social networks. The ever increasing size of the underlying data renders both graph storage and query processing extremely expensive. Sparsification has often been used to reduce the size of deterministic graphs by maintaining only the important edges. However, adaptation of deterministic sparsification methods fails in the uncertain setting. To overcome this problem, we introduce the first sparsification techniques aimed explicitly at uncertain graphs. The proposed methods reduce the number of edges and redistribute their probabilities in order to decrease the graph size, while preserving its underlying structure. The resulting graph can be used to efficiently and accurately approximate any query and mining tasks on the original graph. An extensive experimental evaluation with real and synthetic datasets illustrates the effectiveness of our techniques on several common graph tasks, including clustering coefficient, page rank, reliability, and shortest path distance.

My favorite graph theory conjectures involve the effects of edge removal on the diameter of a graph and the effects of edge addition on the domination and total domination numbers of a graph. Loosely speaking, “criticality” means that the value of the parameter in question always changes under the graph modification. This chapter presents five conjectures concerning criticality, namely, a conjecture by Sumner and Blitch on the criticality of domination upon edge addition, a conjecture by Murty and Simon on the criticality of diameter upon edge removal, and three conjectures on the criticality of total domination upon edge addition. These last three conjectures involving total domination are closely related, and surprisingly, a solution to one of them would provide a solution to the Murty-Simon Conjecture on diameter.

Even sophisticated techniques start out from simple ideas. Later, in reply to application needs or theoretical problems new concepts are introduced and new formalisations proposed, often to a point where the original simple core is hardly recognizably. In this paper we provide a non-technical introduction to the basic concepts of typed graph transformation systems, completed by a survey of more advanced concepts, and explain some of its history and motivations.

The random networks that are formed in typical elastomer cure or cross-linking reactions obey the statistics of local chemical reactions, but it is the long-range, and not the local, properties of the structures that determine their desirable material properties. Properties such as the gel point and cycle rank are determined by the global structure of a network. Forging a connection between local statistics and global structure has been a challenging problem. Tracking the evolution of random structures during the course of cross-linking reactions has been the object of a considerable body of theoretical research. However, much of this research has ignored the space-filling requirements of the resulting statistically branched structures. As especially emphasized by Gordon and co-workers, the chemical structures that are formed in typical cross-linking reactions can be understood within the context of graph theory. However, a pure mathematical graph has no metrical information, which means that any information on the embedding of the graph in three-space will be impossible to infer from the graph alone. Here it is shown that one can introduce physically meaningful metrical information on the graph structure by imposing a spatial distribution of cross-links and chains from the beginning. This ensures that the resulting statistical networks are capable of being embedded in the space of that generates the distribution.

THE PURPOSE OF THIS PAPER is to describe a procedure for ordering and grouping cities by the magnitude and direction of the flows of goods, people, and communications between them. Current theories of nodal regions and central place hierarchies provide the bases for the recognition of region-wide organization of cities into networks. These two theories were developed by students who recognized that the direction and magnitude of flows associated with social processes are indicators of spatial order in the regional structure of urban society. Whether the flow is local and to the city's hinterland, or regional and to the rank ordering of cities, the notion of central or nodal point is dependent upon the levels of strongest associations within the total flow. 1 The present problem is to develop a method capable of quantifying the degree of association between city pairs in a manner that allows identification of the networks of strongest association. These associations may be in terms of .interactions that occur directly between two cities, or indirectly through one or more intermediary cities. The magnitude of the combined direct and indirect associations is measured by an index that is related to certain concepts of graph theory. This index is used to identify the degree of contact between city pairs and it provides a quantitative basis for grouping cities. The resulting subgroups of cities are analogous to nodal regions. When each city in a study region is assigned to a subgroup, it is possible to specify the rank ordering of cities and to evaluate the functional relations of the nodal hierarchy. In this paper, pertinent geograrphic and graph theoretic concepts are discussed and are then used as a basis for deriving the method of isolating nodal regions. Wihile this method is illustrated by the use of intercity telephone calls in Washington state, the techniques are quite general and may be adapted to

We present two new approximation algorithms for the problem of finding a k-node connected spanning subgraph (directed or undirected) of minimum cost. The best known approximation guarantees for this problem were $O(\min \{k,\frac{n}{\sqrt{n-k}}\})$ for both directed and undirected graphs, and $O(\ln k)$ for undirected graphs with $n \geq 6k^2$, where $n$ is the number of nodes in the input graph. Our first algorithm has approximation ratio $O(\frac{n}{n-k}\ln^2 k)$, which is $O(\ln^2 k)$ except for very large values of $k$, namely, $k=n-o(n)$. This algorithm is based on a new result on $\ell$-connected $p$-critical graphs, which is of independent interest in the context of graph theory. Our second algorithm uses the primal-dual method and has approximation ratio $O(\sqrt{n} \ln k)$ for all values of $n,k$. Combining these two gives an algorithm with approximation ratio $O(\ln k \cdot \min \{\sqrt{k},\frac{n}{n-k} \ln k\})$, which asymptotically improves the best known approximation guarantee for directed graphs for all values of $n,k$, and for undirected graphs for $k>\sqrt{n/6}$. Moreover, this is the first algorithm that has an approximation guarantee better than $\Theta(k)$ for all values of $n,k$. Our approximation ratio also provides an upper bound on the integrality gap of the standard LP-relaxation.

There is a large, popular, and growing literature on "scale-free" networks with the Internet along with metabolic networks representing perhaps the canonical examples. While this has in many ways reinvigorated graph theory, there is unfortunately no consistent, precise definition of scale-free graphs and few rigorous proofs of many of their claimed properties. In fact, it is easily shown that the existing theory has many inherent contradictions and that the most celebrated claims regarding the Internet and biology are verifiably false. In this paper, we introduce a structural metric that allows us to differentiate between all simple, connected graphs having an identical degree sequence, which is of particular interest when that sequence satisfies a power law relationship. We demonstrate that the proposed structural metric yields considerable insight into the claimed properties of SF graphs and provides one possible measure of the extent to which a graph is scale-free. This structural view can be related t...

Citation graphs representing a body of scientific literature convey measures of scholarly activity and productivity. In this work we present a study of the structure of the citation graph of the computer science literature. Using a web robot we built several topic-specific citation graphs and their union graph from the digital library ResearchIndex. After verifying that the degree distributions follow a power law, we applied a series of graph theoretical algorithms to elicit an aggregate picture of the citation graph in terms of its connectivity. We discovered the existence of a single large weakly-connected and a single large biconnected component, and confirmed the expected lack of a large strongly-connected component. The large components remained even after removing the strongest authority nodes or the strongest hub nodes, indicating that such tight connectivity is widespread and does not depend on a small subset of important nodes. Finally, minimum cuts between authority papers of different areas did not result in a balanced partitioning of the graph into areas, pointing to the need for more sophisticated algorithms for clustering the graph.

In our previous paper (J. Combin. Theory Ser. A 103 (2) (2003) 387) we formulated a conditional chromatic number theorem, which described a setting in which the chromatic number of the plane takes on two different values depending upon the axioms for set theory. We also constructed an example of a distance graph on the real line R whose chromatic number depends upon the system of axioms we choose for set theory. Ideas developed there are extended in the present paper to construct a distance graph G2 on the plane R2, thus coming much closer to the setting of the chromatic number of the plane problem. The chromatic number of G2 is 4 in the Zermelo–Fraenkel–Choice system of axioms, and is not countable (if it exists) in a consistent system of axioms with limited choice, studied by Solovay (Ann. Math. 92 Ser. 2 (1970) 1).

In this paper, we prove that any edge-coloring critical graph G with maximum degree Δ⩾(11+49−24ε)/2, where ε⩽1, has the size at least 3(|V(G)|−ε)+1 if δ⩽7 or if δ⩾8 and |V(G)|>2Δ−δ−4−(Δ+6)/(δ−6), where δ is the minimum degree of G. It generalizes a result of Sanders and Zhao.

The evolution of the telecommunication technology, such as mobile telecommunication equipment, radio, television, teleconferencing, etc necessitated the existence of numerously broadcast channels. However the corresponding frequencies may interfere for reason of distance, geographical or atmospherical structure or for a variety of other factors. In the present paper we give the definition of the graph radio coloring concept which is a graph coloring generalization. We also introduce radio coloring invariants which are of a great practical importance to problems regarding the allocation of diverse frequencies in order to avoid interference occurrences between channel transmissions. A heuristic algorithm that finds approximate values of the radio chromatic number and radio chromatic cost of a given graph is developed and the result of a computational experiment of the proposed algorithm is given. .

We solve several problems in D-Optimal Design Theory using techniques from Graph Theory and Combinatorics. The techniques involve relating the value of a determinant of a 0–1 matrix with the number of certain perfect matchings in a bipartite graph.

Graph Theory is still a relatively young subject, and debate still rages on what material constitutes the core results that any introductory text should include. Bollobás has chosen to introduce graph theory - including recent results - in a way that emphasizes the connections between (for example) the Tutte polynomial of a graph, the partition functions of theoretical physics, and the new knot polynomials, all of which are interconnected.On the other hand, graph theory is also rooted strongly in computing science, where it is applied to many different problems; Bollobás's treatment is completely theoretical and does not address these applications. Or, in more practical terms, he is concerned whether a solution exists, rather than asking whether the solution can be computed in a reasonably efficient manner.One of the pleasures of working in graph theory is the abundance of problems available to solve. Unlike many more traditional areas of Mathematics, knowing the core results and proofs is frequently insufficient. Often solving a new problem requires a new approach, or a subtle twist on an existing one, combined with some bare knuckle work. Bollobás emphasizes this in the problems available at the end of each chapter; he includes in total 639 problems, ranging from the reasonably straightforward to the very difficult. I spent time with friends working on these problems, and was intrigued by the variety of the proofs that we came up with.

Graph Theory, A natural generalization of graph colouring involves taking colours from a metric space and insisting that the endpoints of an edge receive colours separated by a minimum distance dictated by properties of the edge. In the q-backbone colouring problem, these minimum distances are either q or 1, depending on whether or not the edge is in the backbone. In this paper we consider the list version of this problem, with particular focus on colours in ℤp - this problem is closely related to the problem of circular choosability. We first prove that the list circular q-backbone chromatic number of a graph is bounded by a function of the list chromatic number. We then consider the more general problem in which each edge is assigned an individual distance between its endpoints, and provide bounds using the Combinatorial Nullstellensatz. Through this result and through structural approaches, we achieve good bounds when both the graph and the backbone belong to restricted families of graphs.