In the study of edge colorings of graphs, critical graphs are of particular importance. One classical result concerning the structure of critical graphs is known as Vizing’s Adjacency Lemma. This lemma provides useful structural information about the neighborhood of a vertex in a critical graph. Zhang introduced an adjacency lemma dealing with the second neighborhood of a vertex in a critical graph. Both of these adjacency lemmas are useful tools for proving classification results on edge colorings. In this paper, we present an adjacency lemma on critical signed graphs with even maximum degree. This new adjacency lemma can be interpreted as a local extension of Zhang’s Adjacency Lemma. As an application of the new lemma, we show that a signed planar graph with maximum degree Δ ≥ 6 in which every 6-cycle has at most one chord is Δ -edge-colorable.

We consider the computational complexity of spanning tree problems involving the graphical function-index. This index was recently introduced by Li and Peng as a unification of a long list of chemical and topological indices. We present a number of unified approaches to determine the NP-completeness and APX-completeness of maximum and minimum spanning tree problems involving this index. We give many examples of well-studied topological indices for which the associated complexity questions are covered by our results.

The eccentricity matrix ɛ ( G ) of a strongly connected digraph G is defined as ɛ ( G ) i j = d ( v i , v j ) , if d ( v i , v j ) = min { e + ( v i ) , e − ( v j ) } , 0 , otherwise . , where e + ( v i ) = max { d ( v i , v j ) ∣ v j ∈ V ( G ) } is the out-eccentricity of the vertex v i of G , and e − ( v j ) = max { d ( v i , v j ) ∣ v i ∈ V ( G ) } is the in-eccentricity of the vertex v j of G . The eigenvalue of ɛ ( G ) with the largest modulus is called the eccentricity spectral radius of G . In this paper, we obtain lower bounds for the eccentricity spectral radius among all join digraphs with a fixed dichromatic number. We also give upper bounds for the eccentricity spectral radius of some special join digraphs with a fixed dichromatic number.

Abstract The isolated toughness of a noncomplete graph G is defined as: , where C(G) is the collection of all vertex cutsets of G and i(G − Y) stands for the number of isolated vertices in G − Y. If G is a complete graph, we set . This isolated toughness parameter is closely related to the existence of factors and fractional factors in graphs. These factors and fractional factors are well‐studied within graph theory, and have various applications in several fields related to computer science. In this article, we pay our attention to the computational complexity of computing the isolated toughness. We present polynomial algorithms for computing the exact value of for interval graphs and for split graphs, two well‐studied special graph classes.

For an edge-colored graph, its minimum color degree is the minimum number of distinct colors appearing on the edges incident with a vertex, and its maximum monochromatic degree is the maximum number of edges with the same color incident with a vertex. A cycle in an edge-colored graph is called properly colored if any two consecutive edges of the cycle have distinct colors. We investigate sufficient conditions in terms of the minimum color degree and maximum monochromatic degree for the existence of short properly colored cycles in edge-colored complete graphs. In particular, we obtain sharp results for the existence of properly colored C4’s, and we characterize the extremal graphs for several known results on the existence of properly colored triangles. Moreover, we obtain sharp sufficient conditions guaranteeing that every vertex is contained in a properly colored triangle or C4, respectively.

In the study of cycles and paths, the meta-conjecture of Bondy that sufficient conditions for Hamiltonicity often imply pancyclicity has motivated research on the existence of cycles and paths of many lengths. Hendry further introduced the stronger concepts of cycle extendability and path extendability, which require that every cycle or path can be extended to another one with one additional vertex. These concepts have been studied extensively, but there exist few results on path extendability in digraphs, as far as we know. In this paper, we make the first attempt in this direction. We establish a number of extremal and degree conditions for path extendability in general digraphs. Moreover, we prove that every path of length at least two in a regular tournament is extendable, with some exceptions. One of our proof approaches is a new contraction operation to transform nonextendable paths into nonextendable cycles.

Recently published experimental work on evolution-in-materio applied to nanoscale materials shows promising results for future reconfigurable devices. These experimental results are based on disordered nanoparticle networks, without a predefined design. The material is treated as a black-box, and genetic algorithms are used to find appropriate configuration voltages to enable a targeted functionality. To support future experimental work, we developed simulation tools for predicting candidate functionalities. One of these tools is based on a neural network model, but the one presented here is based on a physical model. The physical model describes the charge transport between the nanoparticles, which is governed by what is known as the Coulomb blockade effect. The new simulation tool combines a genetic algorithm with Monte-Carlo simulations that are based on this physical model. The code of the new simulation tool has been validated with known results on small deterministically designed nanoparticle networks from literature. The code has also been applied to simulate reconfigurable logic in small k χ k grids of nanoparticles. The results show that the new approach has great potential for partly replacing costly and time-consuming experiments.

We first show that for any bipartite graph H with at most five vertices there exists an on-line competitive algorithm for the class of H-free bipartite graphs. We then analyze the performance of an on-line algorithm for coloring bipartite graphs on various subfamilies. The algorithm yields new upper bounds for the on-line chromatic number of bipartite graphs. We prove that the algorithm is on-line competitive for $P_7$-free bipartite graphs, i.e., that do not contain an induced path on seven vertices. The number of colors used by the on-line algorithm for $P_6$-free and $P_7$-free bipartite graphs is, respectively, bounded by roughly twice and roughly eight times the on-line chromatic number. In contrast, it is known that there exists no competitive on-line algorithm to color $P_6$-free (or $P_7$-free) bipartite graphs, i.e., for which the number of colors is bounded by any function depending only on the chromatic number.

This work evaluates an algorithm that maps a number of communicating processes to a heterogeneous tiled system on chip (SoC) architecture at run-time. The mapping algorithm minimizes the total amount of energy consumption, while still providing an adequate quality of service (QoS). A realistic example is mapped using this algorithm.

The availability of high-level design entry tooling is crucial for the viability of any reconfigurable SoC architecture. This paper presents a graph covering algorithm. The graph covering is done in two steps: template generation and template selection. The objective of template generation step is to extract functional equivalent structures, i.e. templates, from a control data flow graph. By inspecting the graph, the algorithm generates all the possible templates and the corresponding matches. Using unique serial numbers and circle numbers, the algorithm can find all distinct templates with multiple outputs. The template selection algorithm shows how this information can be used in compilers for reconfigurable systems. The objective of the template selection algorithm is to find an efficient cover for an application graph with a minimal number of distinct templates and minimal number of matches.

We consider the degree-preserving spanning tree (DPST) problem: Given a connected graph G, find a spanning tree T of G such that as many vertices of T as possible have the same degree in T as in G. This problem is a graph-theoretical translation of a problem arising in the system-theoretical context of identifiability in networks, a concept which has applications in, for example, water distribution networks and electrical networks. We show that the DPST problem is NP-complete, even when restricted to split graphs or bipartite planar graphs, but that it can be solved in polynomial time for graphs with a bounded asteroidal number and for graphs with a bounded treewidth. For the class of interval graphs, we give a linear time algorithm. For the class of cocomparability graphs, we give an O(n4) algorithm. Furthermore, we present linear time approximation algorithms for planar graphs of a worst-case performance ratio of 1 − ϵ for every ϵ > 0. © 2000 John Wiley & Sons, Inc.

Let G be a graph and let t ≥ 0 be a real number. Then, G is t-tough if tω(G − S) ≤ |S| for all S ⊆ V(G) with ω(G − S) > 1, where ω(G − S) denotes the number of components of G − S. The toughness of G, denoted by τ(G), is the maximum value of t for which G is t-tough [taking τ(Kn) = ∞ for all n ≥ 1]. G is minimally t-tough if τ(G) = t and τ(H) < t for every proper spanning subgraph H of G. We discuss how the toughness of (spanning) subgraphs of G and related graphs depends on τ(G), we give some sufficient degree conditions implying that τ(G) ≥ t, and we study which subdivisions of 2-connected graphs have minimally 2-tough squares. © 1999 John Wiley & Sons, Inc. Networks 33: 233–238, 1999

An asteroidal triple (AT) is a set of three vertices such that there is a path between any pair of them avoiding the closed neighborhood of the third. A graph is called AT-free if it does not have an AT. We show that there is an O(n 4 ) time algorithm to compute the maximum weight of an independent set for AT-free graphs. Furthermore, we obtain O(n 4 ) time algorithms to solve the INDEPENDENT DOMINATING SET and the INDEPENDENT PERFECT DOMINATING SET problems on AT-free graphs. We also show how to adapt these algorithms such that they solve the corresponding problem for graphs with bounded asteroidal number in polynomial time. Finally, we observe that the problems CLIQUE and PARTITION INTO CLIQUES remain NP-complete when restricted to AT-free graphs.

Abstract For given nonnegative integers k and D, we consider the problem of determining n0(k, D), The smallest number n for which there exists a k‐regular bipartite graph on n vertices with diameter D. We solve the problem for all pairs (k, D) with D ≢ 2 (mod 4) and D ≢ 3 (mod 4), for all pairs (k, D) with k even or k prime and D ≢ 3 (mod 4), for all pairs with D ≤ 9 or k ≤ 4, and for a few other pairs. in the remaining cases, we obtain lower and upper bounds for n0(k, D).

Abstract Let G = (A, B; E) be a bipartite graph. Let e1, e2 be nonnegative integers, and f1, f2 nonnegative integer‐valued functions on V(G) such that ei ≦ |E| ≦ e1 + e2 and fi(v) ≦ d(v) ≦ f1(v) + f2(v) for all v ϵ V(G) (i = 1, 2). Necessary and sufficient conditions are obtained for G to admit a decomposition in spanning subgraphs G1 = (A, B; E1) and G2 = (A, B; E2) such that |Ei| ≦ ei and dGi(v) ≦ fi(v) for all v ϵ V(G) (i = 1, 2). The result generalizes a known characterization of bipartite graphs with a k‐factor. Its proof uses flow theory and is a refinement of the proof of an analogous result due to Folkman and Fulkerson. By applying corresponding flow algorithms, the described decomposition can be found in polynomial time if it exists. As an application, an assignment problem is solved. © 1993 by John Wiley & Sons, Inc.