Planar Graphs Have Bounded Queue-Number Dujmović, Vida; Joret, Gwenaël; Micek, Piotr ...
Journal of the ACM,
08/2020, Letnik:
67, Številka:
4
Journal Article
Recenzirano
Odprti dostop
We show that planar graphs have bounded queue-number, thus proving a conjecture of Heath et al. 66 from 1992. The key to the proof is a new structural tool called
layered partitions
, and the result ...that every planar graph has a vertex-partition and a layering, such that each part has a bounded number of vertices in each layer, and the quotient graph has bounded treewidth. This result generalises for graphs of bounded Euler genus. Moreover, we prove that every graph in a minor-closed class has such a layered partition if and only if the class excludes some apex graph. Building on this work and using the graph minor structure theorem, we prove that every proper minor-closed class of graphs has bounded queue-number.
Layered partitions have strong connections to other topics, including the following two examples. First, they can be interpreted in terms of strong products. We show that every planar graph is a subgraph of the strong product of a path with some graph of bounded treewidth. Similar statements hold for all proper minor-closed classes. Second, we give a simple proof of the result by DeVos et al. 31 that graphs in a proper minor-closed class have low treewidth colourings.
A new graph product is defined in this paper and several applications of this product are described. The adjacency matrix of the product graph is given and its complete spectrum in terms of the ...spectrum of constituent graphs is determined. Sequences of cospectral graphs can be generated from the known cospectral graphs using the new product. Several sequences of non-cospectral equienergtic graphs can also be generated as an application of the graph product defined.
•Introduces a new spatial-temporal graph product convolutional framework.•Unifies various existing approaches to spatial-temporal graph learning.•Captures multi-scale spatial-temporal features that ...were previously neglected.•Achieves better performance in capturing complex spatial-temporal patterns in two real-world applications.
Earlier works on dynamic spatial-temporal data modelling prefer using spatial-temporal factorized graph convolutional networks (GCNs), which are easy to interpret but fail to capture joint spatial-temporal correlations. Thus, lots of subsequent research focus on constructing a localized adjacent matrix to capture joint features from both spatial and temporal dimension simultaneously. However, their ways of building the adjacent matrices are usually heuristic, which makes the models difficult to interpret. Meanwhile, the lack of theoretical explanations hinders the model’s generalization. We introduce a general framework to model dynamic spatial-temporal graph data from the view of graph product. With the power of graph product, we propose a systematical way of constructing the spatial-temporal adjacent graphs, which can not only improve the model’s interpretability but increase the spatial-temporal receptive field. Under the novel framework, the existing methods can be taken as special cases of our model. Extensive experiments on multiple large-scale real-world datasets, NTU-RGB+D60, NTU-RGB+D120, UAV-Human, PEMS03, PEMS04, PEMS07, and PEMS08, demonstrate that the proposed model can generalize to most of the scenarios with a performance improvement in a significant margin compared to the state-of-the-art methods.
On graph products of monoids Dandan, Yang; Gould, Victoria
Journal of algebra,
04/2023, Letnik:
620
Journal Article
Recenzirano
Odprti dostop
Graph products of monoids provide a common framework for direct and free products, and graph monoids (also known as free partially commutative monoids). If the monoids in question are groups then any ...graph product is a group. For monoids that are not groups, regularity is perhaps the first and most important algebraic property that one considers: however, graph products of regular monoids are not in general regular. We show that a graph product of regular monoids satisfies the related, but weaker, condition of being abundant. More generally, we show that the classes of left abundant and left Fountain monoids are closed under graph product. As a very special case we obtain the earlier result of Fountain and Kambites that the graph product of right cancellative monoids is right cancellative. To achieve our aims we show that elements in (arbitrary) graph products have a unique Foata normal form, and give some useful reduction results; these may equally well be applied to groups as to the broader case of monoids.
On The Energy of Some Composite Graphs Nechirvan B. Ibrahim
Science journal of University of Zakho (Online),
09/2018, Letnik:
3, Številka:
1
Journal Article
Recenzirano
Odprti dostop
Eigenvalues of a graph are the eigenvalues of its adjacency matrix. The energy of a graph is the sum of the absolute values of its eigenvalues, was studied by (Gutman 1978 ). This paper divided in to ... three parts, in part one spectra and nullity of graphs are defined ( Brouwer and Haemers, 2012) and (Harary, 1969). In the second part graph products an their spectra is studied (Shibata and Kikuchi 2000) and (Balakrishnan and Ranganathan , 2012). In the last part, we proves the energy of some graph products including Cartesian, tensor, strong, skew and inverse skew which are applied of some graphs.
In this paper we examine the connections between equistable graphs, general partition graphs and triangle graphs. While every general partition graph is equistable and every equistable graph is a ...triangle graph, not every triangle graph is equistable, and a conjecture due to Jim Orlin states that every equistable graph is a general partition graph. The conjecture holds within the class of chordal graphs; if true in general, it would provide a combinatorial characterization of equistable graphs.
Exploiting the combinatorial features of triangle graphs and general partition graphs, we verify Orlin’s conjecture for several graph classes, including AT-free graphs and various product graphs. More specifically, we obtain a complete characterization of the equistable graphs that are non-prime with respect to the Cartesian or the tensor product, and provide some necessary and sufficient conditions for the equistability of strong, lexicographic and deleted lexicographic products. We also show that the general partition graphs are not closed under the strong product, answering a question by McAvaney et al.
Given a graph G, a set S of vertices in G is a general position set if no triple of vertices from S lie on a common shortest path in G. The general position achievement/avoidance game is played on a ...graph G by players A and B who alternately select vertices of G. A selection of a vertex by a player is a legal move if it has not been selected before and the set of selected vertices so far forms a general position set of G. The player who picks the last vertex is the winner in the general position achievement game and is the loser in the avoidance game. In this paper, we prove that the general position achievement/avoidance games are PSPACE-complete even on graphs with diameter at most 4. For this, we prove that the misère play of the classical Node Kayles game is also PSPACE-complete. As positive results, we obtain linear time algorithms to decide the winning player of the general position avoidance game in rook's graphs, grids, cylinders, and lexicographic products with complete second factors.
Given a graph G on n vertices, a subset of vertices U⊆V(G) is dominating if every vertex of V(G) is either in U or adjacent to a vertex of U. The domination polynomial of G is the generating function ...whose coefficients are the number of dominating sets of a given size. In 2014, Alikhani and Peng conjectured that the domination polynomial is unimodal, i.e., its coefficients are non-decreasing and then non-increasing. We prove unimodality for spider graphs with at most 400 legs (of arbitrary length), lollipop graphs, arbitrary direct products of complete graphs, and Cartesian products of two complete graphs. We show that for every graph, a portion of the coefficients are non-increasing, and, for certain graphs with low upper domination number, this is sufficient to prove unimodality. Furthermore, we show that for graphs with m universal vertices, i.e., vertices of degree n−1, the last 2−m−1(2m−1)n coefficients of their domination polynomial are non-increasing.
PDF
