Search

Infinite analogues of the Paley graphs are constructed, based on uncountably many infinite but locally finite fields. Weil's estimate for character sums shows that they are all isomorphic to the random or universal graph of Erd\H os, R\'enyi and Rado. Automorphism groups and connections with model theory are considered., Comment: 10 pages/

A graph U is an induced universal graph for a family F of graphs if every graph in F is a vertex-induced subgraph of U . Recently, for the family of all undirected graphs on n vertices, Alon [Geom. Funct. Anal. 2017] [3] proved the existence of an induced universal graph with ( 1 + o ( 1 ) ) ⋅ 2 ( n − 1 ) ∕ 2 vertices improving the previous best bound of 16 ⋅ 2 n ∕ 2 by Alstrup et al. (2015) and matching the lower bound of 2 ( n − 1 ) ∕ 2 by Moon (1965) up to lower order additive terms. We continue this line of research of finding the size of the smallest induced universal graph up to lower order additive terms for some basic graph families. For the family of graphs with n vertices and bounded degree D = O ( 1 ) , Alon and Nenadov [Math. Proc. Camb. Philos. Soc. 2017] [4] showed that the smallest induced universal graph has size Θ n D ∕ 2 , but it remains to find the constant hidden in the O -notation. For even D the bound O n D ∕ 2 was already shown by Butler (2009). In order to find the correct constants for general D > 0 , it is natural first to consider the case D = 2 . For D = 2 , Butler gave an induced universal graph of size 6 . 5 n and subsequently, Esperet et al. (2008) found an induced universal graph for D = 2 of size 2 . 5 n . We construct for D = 2 an even smaller induced universal graph with 2 n − 1 vertices. This proves a conjecture by Esperet et al. stating the existence of such a graph with 2 n + o ( n ) vertices. For the family of acyclic graphs on n vertices with maximum degree 2 we show that the smallest induced universal graph has size 3 n 2 . We also introduce the notion of size oblivious and size aware decoding, and relate this to families of induced universal graphs. For the family of graphs consisting of a single cycle we prove new upper and lower bounds on the complexity of size aware and size oblivious decoders. These new bounds separate the two notions.

We investigate three formalisms to specify graph languages, i.e. sets of graphs, based on type graphs. First, we are interested in (pure) type graphs, where the corresponding language consists of all graphs that can be mapped homomorphically to a given type graph. In this context, we also study languages specified by restriction graphs and their relation to type graphs. Second, we extend this basic approach to a type graph logic and, third, to type graphs with annotations. We present decidability results and closure properties for each of the formalisms., (v2): -Fixed some typos -Added more references

Motivated by the prevalent data science applications of processing and mining large-scale graph data such as social networks, web graphs, and biological networks, as well as the high I/O and communication costs of storing and transmitting such data, this paper investigates lossless compression of data appearing in the form of a labeled graph. A universal graph compression scheme is proposed, which does not depend on the underlying statistics/distribution of the graph model. For graphs generated by a stochastic block model, which is a widely used random graph model capturing the clustering effects in social networks, the proposed scheme achieves the optimal theoretical limit of lossless compression without the need to know edge probabilities, community labels, or the number of communities. The key ideas in establishing universality for stochastic block models include: 1) block decomposition of the adjacency matrix of the graph; 2) generalization of the Krichevsky-Trofimov probability assignment, which was initially designed for i.i.d. random processes. In four benchmark graph datasets (protein-to-protein interaction, LiveJournal friendship, Flickr, and YouTube), the compressed files from competing algorithms (including CSR, Ligra+, PNG image compressor, and Lempel-Ziv compressor for two-dimensional data) take 2.4 to 27 times the space needed by the proposed scheme.

A classic application of description length is for model selection with the minimum description length (MDL) principle. The focus of this paper is to extend description length for data analysis beyond simple model selection and sequences of scalars. More specifically, we extend the description length for data analysis in Gaussian graphical models. These are powerful tools to model interactions among variables in a sequence of i.i.d Gaussian data in the form of a graph. Our method uses universal graph coding methods to accurately account for model complexity, and therefore provide a more rigorous approach for graph model selection. The developed method is tested with synthetic and electrocardiogram (ECG) data to find the graph model and anomaly in Gaussian graphical models. The experiments show that our method gives better performance compared to commonly used methods., Comment: Submitted to ISIT 2021

It is well-known that the winning region of a parity game with $n$ nodes and $k$ priorities can be computed as a $k$-nested fixpoint of a suitable function; straightforward computation of this nested fixpoint requires $\mathcal{O}(n^{\frac{k}{2}})$ iterations of the function. Calude et al.'s recent quasipolynomial-time parity game solving algorithm essentially shows how to compute the same fixpoint in only quasipolynomially many iterations by reducing parity games to quasipolynomially sized safety games. Universal graphs have been used to modularize this transformation of parity games to equivalent safety games that are obtained by combining the original game with a universal graph. We show that this approach naturally generalizes to the computation of solutions of systems of \emph{any} fixpoint equations over finite lattices; hence, the solution of fixpoint equation systems can be computed by quasipolynomially many iterations of the equations. We present applications to modal fixpoint logics and games beyond relational semantics. For instance, the model checking problems for the energy $\mu$-calculus, finite latticed $\mu$-calculi, and the graded and the (two-valued) probabilistic $\mu$-calculus -- with numbers coded in binary -- can be solved via nested fixpoints of functions that differ substantially from the function for parity games but still can be computed in quasipolynomial time; our result hence implies that model checking for these $\mu$-calculi is in QP. Moreover, we improve the exponent in known exponential bounds on satisfiability checking., Comment: extended version of conference paper

A subgraph $H$ of a graph $G$ is isometric if the distances between vertices in $H$ coincide with the distances between the corresponding vertices in $G$. We show that for any integer $n\ge 1$, there is a graph on $3^{n+O(\log^2 n)}$ vertices that contains isometric copies of all $n$-vertex graphs. Our main tool is a new type of distance labelling scheme, whose study might be of independent interest., Comment: 13 pages, no figure. v2: revised version

Deep learning has been successful in many fields such as acoustics, image, and natural language processing. However, due to the unique characteristics of graphs, deep learning using universal graph data is not easy. The Graph Attention Networks (GATs) show the best performance in multiple authoritative node classification benchmark tests (including transductive and inductive). The purpose of this research is to design and implement an FPGA-based accelerator called S-GAT for graph attention networks that achieves excellent performance on acceleration and energy efficiency without losing accuracy, and does not rely on DSPs and large amounts of on-chip memory. We design S-GAT with software and hardware co-optimization. Specifically, we use model compression and feature quantization to reduce the model size, and use shift addition units (SAUs) to convert multiplication into shift operation to further reduce the computation requirements. We integrate the above optimizations into a universal hardware pipeline for various structures of GATs. At last, we evaluate our design on an Inspur F10A board with an Intel Arria 10 GX1150 and 16 GB DDR3 memory. Experimental results show that S-GAT can achieve 7.34 times speedup over Nvidia Tesla V100 and 593 times over Xeon CPU Gold 5115 while maintaining accuracy, and 48 times and 2400 times on energy efficiency respectively.

In the vast literature on waves and plasma interaction, the skin depth, the stochastic heating and the radiofrequency (rf) magnetic field effects emerge as important factors in simulations, still relying on effective collision rate models: a closed form and universal graph are given for stochastic heating. A simulation code based on iteration between plasma and rf calculations is recalled, and typical results are shown, for a simple induction ion source design.

We suggest a combinatorial classification of metric filtrations of measure spaces; a complete invariant of such a filtration is its combinatorial scheme, a measure on the space of hierarchies of the group Z. In turn, the notion of a combinatorial scheme is a source of new metric invariants of automorphisms approximated by means of basic filtrations. We construct a universal graph with an adic structure such that every automorphism can be realized on its path space.

We first prove that for every vertex x of a 4-connected graph G there exists a subgraph H in G isomorphic to a subdivision of the complete graph K4 on four vertices such that G-V(H) is connected and contains x. This implies an affirmative answer to a question of W. Kuehnel whether every 4-connected graph G contains a subdivision H of K4 as a subgraph such that G-V(H) is connected. The motor for our induction is a result of Fontet and Martinov stating that every 4-connected graph can be reduced to a smaller one by contracting a single edge, unless the graph is the square of a cycle or the line graph of a cubic graph. It turns out that this is the only ingredience of the proof where 4-connectedness is used. We then generalize our result to connected graphs of minimum degree at least 4, by developing the respective motor: A structure theorem for the class of simple connected graphs of minimum degree at least 4.

We study the local k-coloring of graphs.We prove that it is NP-complete to determine whether a graph has a local k-coloring for fixed k=4 or k=2t1, where t3.We prove that it is NP-complete to determine whether a planar graph has a local 5-coloring even restricted to the maximum degree =7or8. A local k-coloring of a graph G is a function f:V(G){1,2,,k} such that for each SV(G), 2|S|3, there exist u,vS with |f(u)f(v)| at least the size of the subgraph induced by S. The local chromatic number of G is (G)=min{k:Ghas a localk-coloring}. In this paper, we show that it is NP-complete to determine whether a graph has a local k-coloring for fixed k=4 or k=2t1, where t3. In particular, it is NP-complete to determine whether a planar graph has a local 5-coloring even restricted to the maximum degree =7or8.

It is shown to be consistent with various values of b , d and 2 ℵ 1 that there is a universal graph on ω 1 . Moreover, it is also shown that it is consistent that there is a universal graph on ω 1 — in other words, a universal symmetric function from ω 1 2 to 2 — but no such function from ω 1 2 to ω. The method used relies on iterating well known reals, such as Miller and Laver reals, and alternating this with the PID forcing which adds no new reals. The last sections examine the question of set valued universal functions.

Let H={H1,,Hk} be a set of connected graphs. A graph is said to be H-free if it does not contain any member of H as an induced subgraph. We show that if the following statements hold, |H|2,K1,3H,for any integer n0, every 2-connected H-free graph G of order at least n0 is supereulerian, i.e.,G has a spanning closed trail,then H{K1,3} contains an Ni,j,k or a path where Ni,j,k denotes the graph obtained by attaching three vertex-disjoint paths of lengths i,j,k0 to a triangle.As an application, we characterize all the forbidden triples H with K1,3H such that every 2-connected H-free graph is supereulerian. As a byproduct, we also characterize minimal 2-connected non-supereulerian claw-free graphs.

In Knor et al. (2016) authors conjectured that for a graph G , W min ( G ) is achieved for a χ ( G ) -coloring-induced orientation. They also proved the conjecture holds for bipartite graphs, complete graphs, prisms and Petersen graph. However, we find that there exists a graph G such that any minimum Wiener index orientation of G is not χ ( G ) -coloring-induced. This means the conjecture does not hold in general. Furthermore, we explore some graphs which do not satisfy the conjecture.

Let GA be a hereditary family of graphs and H a family of acyclically directed graphs. A graph G ( V , E ) is a GA-H reduced graph if it can be obtained from a graph GA ( V , D ) ∈ GA by deleting the edges of an edge subgraph H ( V , E ′ ) ∈ H . The present paper complements reference [9] by proving that the following properties are equivalent: Property 1: u → v ∈ E ′ implies N GA [ u ] ⊆ N GA [ v ] . Property 2: u → v ∈ E ′ and v — w ∉ E ∪ E ′ = D implies u — w ∉ E ∪ E ′ = D . This equivalence implies that most of the algorithms in the above reference apply to the GA-H reduced graphs where H is the family of transitive edge subgraphs of the closed neighborhoods containment graphs of the graphs in GA. We also describe a polynomial time algorithm for maximum weight independent set under the weaker condition that H ( V , E ′ ) is a locally transitive edge subgraph of the closed neighborhoods containment graph of GA ( V , D ) .

We study strong graph bundles : a concept imported from topology which generalizes both covering graphs and product graphs. Roughly speaking, a strong graph bundle always involves three graphs E , B and F and a projection p : E → B with fiber F (i.e. p − 1 x ≅ F for all x ∈ V ( B ) ) such that the preimage of any edge x y of B is trivial (i.e. p − 1 x y ≅ K 2 ⊠ F ). Here we develop a framework to study which subgraphs S of B have trivial preimages (i.e. p − 1 S ≅ S ⊠ F ) and this allows us to compare and classify several variations of the concept of strong graph bundle. As an application, we show that the clique operator preserves triangular graph bundles (strong graph bundles where preimages of triangles are trivial) thus yielding a new technique for the study of clique divergence of graphs.

It is well-known that the paths are determined by the spectrum of the adjacency matrix. For digraphs, every digraph whose underlying graph is a tree is cospectral to its underlying graph with respect to the Hermitian adjacency matrix ( H -cospectral). Thus every (simple) digraph whose underlying graph is isomorphic to P n is H -cospectral to P n . Interestingly, there are others. This paper finds digraphs that are H -cospectral with the path graph P n and whose underlying graphs are nonisomorphic, when n is odd, and finds that such graphs do not exist when n is even. In order to prove this result, all digraphs whose Hermitian spectral radius is smaller than 2 are determined.

A connected graph G = ( V , E ) with m edges is called universal antimagic if for each set B of m positive integers there is an bijective function f : E → B such that the function f ˜ : V → N defined at each vertex v as the sum of all labels of edges incident to v is injective. In this work we prove that several classes of graphs are universal antimagic. Among others, paths, cycles, split graphs, and any graph which contains the complete bipartite graph K 2 , n as a spanning subgraph.

The shift graph G S is defined on the space of infinite subsets of natural numbers by letting two sets be adjacent if one can be obtained from the other by removing its least element. We show that this graph is not a minimum among the graphs of the form G f defined on some Polish space X , where two distinct points are adjacent if one can be obtained from the other by a given Borel function f : X → X . This answers the primary outstanding question from [8] .

A graph is nonsingular if its adjacency matrix A(G) is nonsingular. The inverse of a nonsingular graph G is a graph whose adjacency matrix is similar to A(G)−1 via a particular type of similarity. Let H denote the class of connected bipartite graphs with unique perfect matchings. Tifenbach and Kirkland (2009) characterized the unicyclic graphs in H which possess unicyclic inverses. We present a characterization of unicyclic graphs in H which possess bicyclic inverses.

Starting from a supercompact cardinal we build a model in which 2 ℵ ω 1 = 2 ℵ ω 1 + 1 = ℵ ω 1 + 3 but there is a jointly universal family of size ℵ ω 1 + 2 of graphs on ℵ ω 1 + 1 . The same technique will work for any uncountable cardinal in place of ω 1 .

We present a new method to construct a family of co-spectral graphs. Our method is based on a new type of graph product that we define, the bipartite graph product, which may be of self-interest. Our method is different from existing techniques in the sense that it is not based on a sequence of local graph operations (e.g. Godsil–McKay switching). The explicit nature of our construction allows us, for example, to construct an infinite family of cospectral graphs and provide an easy proof of non-isomorphism. We are also able to characterize fully the spectrum of the cospectral graphs.

Let d 1 , d 2 , … , d k be k non-negative integers. A graph G is ( d 1 , d 2 , … , d k ) -colorable, if the vertex set of G can be partitioned into subsets V 1 , V 2 , … , V k such that the subgraph G [ V i ] induced by V i has maximum degree at most d i for i = 1 , 2 , … , k . In this paper, we prove that every planar graph without cycles of length 4 or 9 is ( 1 , 1 , 0 ) -colorable.

We study the following conjecture of Matt DeVos: If there is a graph homomorphism from a Cayley graph $\mathrm{Cay}(M, B)$ to another Cayley graph $\mathrm{Cay}(M', B')$ then every graph with an $(M,B)$-flow has an $(M',B')$-flow. This conjecture was originally motivated by the flow-tension duality. We show that a natural strengthening of this conjecture does not hold in all cases but we conjecture that it still holds for an interesting subclass of them and we prove a partial result in this direction. We also show that the original conjecture implies the existence of an oriented cycle double cover with a small number of cycles.

A graph with some graph symmetry property is top, if it cannot be viewed as a nontrivial normal quotient of some other graph with the same graph symmetry property. Therefore, a graph being top implies that it has no nontrivial normal multicovers, including normal covers. John Conway proved that every s-arc-transitive graph has a nontrivial s-arc-transitive normal cover, so there is no top s-arc-transitive graph. However, there exist top locally-s-distance-transitive graphs, and complete multipartite graphs are examples of this. In this paper, we give a generic condition for locally-s-distance-transitive graphs to be top. Also, examples and characterizations of graphs that admit this condition are given.

It was recently discovered (Gutman etal., 2015) that the coindex of the first Zagreb index of any graph is equal to the coindex of the complement of this graph. We examine the possibility that an analogous equality holds for other topological indices. It is shown that there are several classes of graphs and classes of topological indices for which such a relation is obeyed.

A graph G of order n is called arbitrarily partitionable (AP, for short) if, for every sequence ( n 1 , … , n k ) of positive integers with n 1 + … + n k = n , there exists a partition ( V 1 , … , V k ) of the vertex set V ( G ) such that V i induces a connected subgraph of order n i , for i = 1 , … , k . In this paper we consider the on-line version of this notion, defined in a natural way. We prove that if G is a connected graph such with the independence number at most ⌈ n 2 ⌉ and the degree sum of any pair of non-adjacent vertices is at least n − 3 , then G is on-line arbitrarily partitionable except for two graphs of small orders. We also prove that if G is a connected graph of order n and size ‖ G ‖ > n − 3 2 + 6 , then G is on-line AP unless n is even and G is a spanning subgraph of a unique exceptional graph. These two results imply that dense AP graphs satisfying one of the above two assumptions are also on-line AP. This is in contrast to sparse graphs where only few AP graphs are also on-line AP.

The union of n node-disjoint triangles and a Hamiltonian cycle on the same node set is called a cycle-plus-triangles graph. Du, Hsu and Hwang conjectured that every such graph has independence number n . The conjecture was later strengthened by Erdős claiming that every cycle-plus-triangles graph has a 3 -colouring, which was verified by Fleischner and Stiebitz using the Combinatorial Nullstellensatz. An elementary proof was later given by Sachs. However, these proofs are non-algorithmic and the complexity of finding a proper 3 -colouring is left open. As a first step toward an algorithm, we show that it can be decided in polynomial time whether a graph is a cycle-plus-triangles graph. Our algorithm is based on revealing structural properties of cycle-plus-triangles graphs.

In this article we consider the relationship between vertex coloring and the immersion order. Specifically, a conjecture proposed by Abu-Khzam and Langston in 2003, which says that the complete graph with t vertices can be immersed in any t -chromatic graph, is studied. First, we present a general result about immersions and prove that the conjecture holds for graphs whose complement does not contain any induced cycle of length four and also for graphs having the property that every set of five vertices induces a subgraph with at least six edges. Then, we study the class of all graphs with independence number less than three, which are graphs of interest for Hadwiger’s Conjecture. We study such graphs for the immersion-analog. If Abu-Khzam and Langston’s conjecture is true for this class of graphs, then an easy argument shows that every graph of independence number less than 3 contains K n 2 as an immersion. We show that the converse is also true. That is, if every graph with independence number less than 3 contains an immersion of K n 2 , then Abu-Khzam and Langston’s conjecture is true for this class of graphs. Furthermore, we show that every graph of independence number less than 3 has an immersion of K n 3 .

The adjacency spectrum of a graph , which is denoted by Spec(), is the multiset of eigenvalues of its adjacency matrix. We say that two graphs and are cospectral if Spec()=Spec(). In this paper for each prime number p, p23, we construct a large family of cospectral non-isomorphic Cayley graphs over the dihedral group of order 2p.

We describe an algorithm for generating all k-critical H-free graphs, based on a method of Hoang et al. (A graph G is k-critical H-free if G is H-free, k-chromatic, and every H-free proper subgraph of G is (k−1)-colorable). Using this algorithm, we prove that there are only finitely many 4-critical (P7,Ck)-free graphs, for both k=4 and k=5. We also show that there are only finitely many 4-critical (P8,C4)-free graphs. For each of these cases we also give the complete lists of critical graphs and vertex-critical graphs. These results generalize previous work by Hell and Huang, and yield certifying algorithms for the 3-colorability problem in the respective classes. In addition, we prove a number of characterizations for 4-critical H-free graphs when H is disconnected. Moreover, we prove that for every t, the class of 4-critical planar Pt-free graphs is finite. We also determine all 52 4-critical planar P7-free graphs. We also prove that every P11-free graph of girth at least five is 3-colorable, and show that this is best possible by determining the smallest 4-chromatic P12-free graph of girth at least five. Moreover, we show that every P14-free graph of girth at least six and every P17-free graph of girth at least seven is 3-colorable. This strengthens results of Golovach et al.

Let H be a graph. A graph G = ( V , E ) admits an H -covering if every edge in E belongs to a subgraph of G isomorphic to H . A graph G admitting an H -covering is called ( a , d ) - H -antimagic if there is a bijection f : V ( G ) ∪ E ( G ) → { 1 , 2 , … , | V ( G ) | + | E ( G ) | } such that for each subgraph H ′ of G isomorphic to H , the sum of labels of all the edges and vertices belonged to H ′ constitute the arithmetic progression with the initial term a and the common difference d . Such a graph is called super if f ( V ( G ) ) = { 1 , 2 , 3 , … , | V ( G ) | } . In this paper, we provide two constructions of (super) H -antimagic graphs obtained from smaller (super) H ′ -antimagic graphs.

Graph is widely used to model data in various applications. With the rapid growth of many emerging applications such as Internet of Things, it is urgent to require the processing capability on large scale graphs with billions of vertices. Web graph is a typical case of graph data that is widely used for analyzing the structure, behavior and evolution of the World Wide Web. In this paper, we focus on optimal representation of large-scale Web graphs. Our work is motivated by the need of fit large-scale graphs into the main memory and carry out analyze on them. By analyzing the adjacency matrix of Web graphs, we find two characteristics on the distribution of 1s in the matrix. Firstly, only a very small proportion of elements in the matrix are 1s. Secondly, majority of 1s gather around the principal diagonal and form a few number of clusters in the matrix. Based on these characteristics, we first develop a clustering mechanism to locate the clusters of 1s in the adjacency matrix. Then, we combine this clustering mechanism with a structure named K2-tree and propose an approach for representing large-scale Web graphs compactly. Basic idea of the approach is trying to compress a large number of zeros as a single zero. Experimental results show that, our approach not only reduces the space for representing a Web graph, but also reduces the time consumption for operations such as retrieving neighbors of any nodes on the graph; compared with existing approaches, our approach achieves the best space/time tradeoff.

Subgraph enumeration, which aims to find all the subgraphs of a large data graph that are isomorphic to a given pattern graph, is a fundamental graph problem with a wide range of applications. However, existing sequential algorithms for subgraph enumeration fall short in handling large graphs due to the involvement of computationally intensive subgraph isomorphism operations. Thus, some recent researches focus on solving the problem using MapReduce. Nevertheless, exiting MapReduce approaches are not scalable to handle very large graphs since they either produce a huge number of partial results or consume a large amount of memory. Motivated by this, in this paper, we propose a new algorithm $$\mathsf {Twin}$$Twin$$\mathsf {Twig}$$Twig$$\mathsf {Join}$$Join based on a left-deep-join framework in MapReduce, in which the basic join unit is a $$\mathsf {Twin}$$Twin$$\mathsf {Twig}$$Twig (an edge or two incident edges of a node). We show that in the Erdos---Renyi random graph model, $$\mathsf {Twin}$$Twin$$\mathsf {Twig}$$Twig$$\mathsf {Join}$$Join is instance optimal in the left-deep-join framework under reasonable assumptions, and we devise an algorithm to compute the optimal join plan. We further discuss how our approach can be adapted to handle the power-law random graph model. Three optimization strategies are explored to improve our algorithm. Ultimately, by aggregating equivalent nodes into a compressed node, we construct the compressed graph, upon which the subgraph enumeration is further improved. We conduct extensive performance studies in several real graphs, one of which contains billions of edges. Our approach significantly outperforms existing solutions in all tests.

The Erd?s---Sos Conjecture states that every graph with average degree more than $$k-2$$k-2 contains all trees of order k as subgraphs. In this paper, we consider a variation of the above conjecture: studying the maximum size of an (n, m)-bipartite graph which does not contain all (k, l)-bipartite trees for given integers $$n\ge m$$n?m and $$k\ge l$$k?l. In particular, we determine that the maximum size of an (n, m)-bipartite graph which does not contain all (n, m)-bipartite trees as subgraphs (or all (k, 2)-bipartite trees as subgraphs, respectively). Furthermore, all these extremal graphs are characterized.

A connected graph is called Q-controllable if its signless Laplacian eigenvalues are mutually distinct and main. Two graphs G and H are said to be Q-cospectral if they share the same signless Laplacian spectrum. In this paper, infinite families of Q-controllable graphs are constructed, by using the operator of rooted product introduced by Godsil and McKay. In the process, innitely many non-isomorphic Q-cospectral graphs are also constructed, especially, including those graphs whose signless Laplacian eigenvalues are mutually distinct.

The energy of a graph is defined as the sum of the absolute values of all eigenvalues of the graph. The subgraph grafting operation on a graph is a kind of subgraph moving between two vertices of the graph. In this paper, we introduce two new subgraph grafting operations on bipartite graph and show how the graph energy changes under these subgraph grafting operations. As the application of these operations, we determine the trees with the third and fourth minimal energies in the set of trees with given order and domination number.

Two graphs are cospectral if their spectra coincide. The set of all graphs that are cospectral to a given graph, including the graph by itself, is the cospectral equivalence class of the graph. We say that a graph is determined by its spectrum, or that it is a DS-graph, if it is a unique graph having that spectrum. Given n reals belonging to the interval [ − 2 , 2 ] , we want to find all graphs on n vertices having these reals as the eigenvalues of the adjacency matrix. Such graphs are called Smith graphs. Our search is based on solving a system of linear Diophantine equations. We present several results on spectral characterizations of Smith graphs.

We propose a Machine reading comprehension (MRC) method based on the Abstract Meaning Representation (AMR) framework and a universal graph alignment algorithm. We combine syntactic, semantic and entity-based graph representations of a question to match it with a combined representation of an answer. The alignment algorithm is applied for combining various representations of the same text as well as for matching (generalization) of two different texts such as a question and an answer. We explore a number of Question Answering (Q/A) configurations and select a scenario where the proposed AMR generalization-based algorithm AMRG detects and rectifies the errors of a traditional neural MRC. When the state-of-the-art neural MRC is applied and delivers the correct answer in almost 90% of cases, the proposed AMRG verifies each answer and if it determines that it is incorrect, attempts to find a correct one. This error-correction scenario boosts the state-of-the-art performance of a neural MRC by at least 4%.

We prove that the universal cover of any graph manifold quasi-isometrically embeds into a product of three trees. In particular we show that the Assouad-Nagata dimension of the universal cover of any closed graph manifold is 3, proving a conjecture of Smirnov., 3 pages, final version - to appear in Proceedings of the AMS

A graph property is a class of graphs which is closed under isomorphisms. Some properties are also closed under one or more specified constructions that extend any graph into a supergraph containing the original graph as an induced subgraph. We introduce and study in particular the concept that a property P “allows finite spiking” and show that there is a universal graph in every induced-hereditary property of finite character which allows finite spiking. We also introduce the concept that P “allows isolated vertex addition” and constructively show that there is a unique graph with the so-called P -extension property in every induced-hereditary property P of finite character which allows finite spiking and allows isolated vertex addition; such a graph is then universal in P too. Infinitely many examples which satisfy the conditions of both these results are obtained by taking the property of K n -free graphs for an arbitrary integer n ≥ 2 .

The Maximum Weight Independent Set Problem (WIS) is a well-known NP-hard problem. A popular way to study WIS is to detect graph classes for which WIS can be solved in polynomial time, with particular reference to hereditary graph classes (i.e., defined by a hereditary graph property), or equivalently to F -free graphs for a given graph family F (i.e., graphs which are F -free for all F ∈ F ). A tool to extend the results which show that for given hereditary graph classes the WIS problem can be solved in polynomial time is given by the following easy proposition: For any graph family F , if WIS can be solved for F -free graphs in polynomial time, then WIS can be solved for K 1 + F -free graphs (i.e., graphs which are K 1 + F -free for all F ∈ F ) in polynomial time. The main result of this paper is the following: A sufficient condition to extend the above proposition to K 2 + F -free graphs, and more generally to l K 2 + F -free graphs for any constant l (i.e., graphs which are l K 2 + F -free for all F ∈ F ), is that F -free graphs are m -plausible for a constant m , i.e., that for any F -free graph G the family of those maximal independent sets I of G such that every vertex of G not in I has more than m neighbors in I can be computed in polynomial time. In this context a section is devoted to show that (for instance) chordal graphs are m -plausible for a constant m . The proof of the main result is based on the idea/algorithm introduced by Farber to prove that every 2 K 2 -free graph has O ( n 2 ) maximal independent sets (Farber, 1989), which directly leads to a polynomial time algorithm to solve WIS for 2 K 2 -free graphs through a dynamic programming approach, and on some extensions of that idea/algorithm.

Given a group Γ and a biased graph ( G , B ) , we define a what is meant by a Γ-realization of ( G , B ) and a notion of equivalence of Γ-realizations. We prove that for a finite group Γ and t ≥ 3 , there are numbers n ( Γ ) and n ( Γ , t ) such that the number of Γ-realizations of a vertically 3-connected biased graph is at most n ( Γ ) and that the number of Γ-realizations of a nonseparable biased graph without a ( 2 C t , ∅ ) -minor is at most n ( Γ , t ) . Other results pertaining to contrabalanced biased graphs are presented as well as an analogue to Whittle's Stabilizer Theorem for Γ-realizations of biased graphs.

The cop-and-robber game is a game between two players, where one tries to catch the other by moving along the edges of a graph. It is well known that on a finite graph the cop has a winning strategy if and only if the graph is constructible and that finiteness is necessary for this result. We propose the notion of weakly cop-win graphs, a winning criterion for infinite graphs which could lead to a generalisation. In fact, we generalise one half of the result, that is, we prove that every constructible graph is weakly cop-win. We also show that a similar notion studied by Chastand et al. (which they also dubbed weakly cop-win) is not sufficient to generalise the above result to infinite graphs. In the locally finite case we characterise the constructible graphs as the graphs for which the cop has a so-called protective strategy and prove that the existence of such a strategy implies constructibility even for non-locally finite graphs.

In this article, we prove three theorems. The first is that every connected graph of order n and size m has an induced forest of order at least (8n−2m−2)/9 with equality if and only if such a graph is obtained from a tree by expanding every vertex to a clique of order either 4 or 5. This improves the previous lower bound 2n22m+n of Alon–Kahn–Seymour for m≤5n/2, and implies that such a graph has an induced forest of order at least n/2 for m

A structural characterization of graphs not containing the Wagner graph, also known as V 8 , is shown. The result was announced in 1979 by the second author, but until now a proof has not been published.

Given two graphs $G$ and $H$, we say that $G$ contains $H$ as an induced minor if a graph isomorphic to $H$ can be obtained from $G$ by a sequence of vertex deletions and edge contractions. We study the complexity of Graph Isomorphism on graphs that exclude a fixed graph as an induced minor. More precisely, we determine for every graph $H$ that Graph Isomorphism is polynomial-time solvable on $H$-induced-minor-free graphs or that it is GI-complete. Additionally, we classify those graphs $H$ for which $H$-induced-minor-free graphs have bounded clique-width. These two results complement similar dichotomies for graphs that exclude a fixed graph as an induced subgraph, minor, or subgraph., Comment: 16 pages, 5 figures. An extended abstract of this paper previously appeared in the proceedings of the 41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2015)