The skewness of a graph G is the minimum number of edges in G whose deletion results in a planar graph. We determine the skewness (i) of the Cartesian product of G with path and cycle and (ii) of the ...join product of G with isolated vertices. Moreover we also classify those that are π-skew from these classes of graphs.
Brooks’ theorem states that for a graph G, if Δ(G)≥3 and ω(G)≤Δ(G), then χ(G)≤Δ(G). In this paper, we show that this chromatic bound can be further strengthened on (P6,C4,H)-free graphs, where ...H∈{bull,diamond}. In particular, we prove that for a (P6,C4,bull)-free graph G, if Δ(G)≥9 and ω(G)≤Δ(G)−1, then χ(G)≤Δ(G)−1. We also prove that for a (P6,C4,diamond)-free graph G, if Δ(G)≥5 and ω(G)≤Δ(G)−1, then χ(G)≤Δ(G)−1. We also show that similar results hold for (P10,paw)-free graphs and (P5,C5)-free graphs. These results validate the Borodin–Kostochka conjecture on these graph classes.
The minimum spanning tree (MST) is widely used in planning the most economical network. The algorithm for finding the MST of a connected graph is essential. In this paper, a new algorithm for finding ...MST is proposed based on a deduced theorem of MST. The algorithm first sorts the edges in the graph according to their weight, from large to small. Next, on the premise of ensuring the connectivity of the graph, it deletes the edges in this order until the number of edges of the graph is equal to the number of vertexes minus 1. Finally, the remaining graph is an MST. This algorithm is equivalent to an inverse Kruskal algorithm. For sparse graphs, the proposed algorithm has higher efficiency than the Kruskal algorithm. Experiments and analysis verify the effectiveness of the algorithm proposed in this paper. The algorithm provides a better choice for finding the MST of the sparse graph.
We present a logspace algorithm for computing a canonical labeling, in fact, a canonical interval representation, for interval graphs. To achieve this, we compute canonical interval representations ...of interval hypergraphs. This approach also yields a canonical labeling of convex graphs. As a consequence, the isomorphism and automorphism problems for these graph classes are solvable in logspace. For proper interval graphs we also design logspace algorithms computing their canonical representations by proper and by unit interval systems.
Analyzing the behavior of complex networks is an important element in the design of new man-made structures such as communication systems and biologically engineered molecules. Because any complex ...network can be represented by a graph, and therefore in turn by a matrix, graph theory has become a powerful tool in the investigation of network performance. This self-contained 2010 book provides a concise introduction to the theory of graph spectra and its applications to the study of complex networks. Covering a range of types of graphs and topics important to the analysis of complex systems, this guide provides the mathematical foundation needed to understand and apply spectral insight to real-world systems. In particular, the general properties of both the adjacency and Laplacian spectrum of graphs are derived and applied to complex networks. An ideal resource for researchers and students in communications networking as well as in physics and mathematics.
We design an O(n3) algorithm to find a minimum weighted coloring of a (P5,P¯5)-free graph. Furthermore, the same technique can be used to solve the same problem for several classes of graphs, defined ...by forbidden induced subgraphs, such as (diamond, co-diamond)-free graphs.
This paper investigates sign-consensus problems of general linear multi-agent systems. The interaction between agents is modeled by a signed directed graph, where both cooperation and competition ...coexist within a group. The graph is allowed to be structurally unbalanced and its adjacency matrix is assumed to be eventually positive. Distributed control laws are proposed for several classes of graph topologies. Simulation examples are provided to illustrate the proposed control laws. Signed graph-based multi-agent systems provide models to opinion dynamics and social networks, and may also hold significance in further developing such internet search algorithms as PageRank to counter spamming websites.
PDF
