(2 + ϵ)‐Coloring of planar graphs with large odd‐girth

The odd‐girth of a graph is the length of a shortest odd circuit. A conjecture by Pavol Hell about circular coloring is solved in this article by showing that there is a function ƒ(ϵ) for each ϵ : 0 < ϵ < 1 such that, if the odd‐girth of a planar graph G is at least ƒ(ϵ), then G is (2 + ϵ)‐colorable. Note that the function ƒ(ϵ) is independent of the graph G and ϵ → 0 if and only if ƒ(ϵ) → ∞. A key lemma, called the folding lemma, is proved that provides a reduction method, which maintains the odd‐girth of planar graphs. This lemma is expected to have applications in related problems. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 109–119, 2000     

The connected partition lattice of a graph and the reconstruction conjecture

Previously we showed that many invariants of a graph can be computed from its abstract induced subgraph poset, which is the isomorphism class of the induced subgraph poset, suitably weighted by subgraph counting numbers. In this paper, we study the abstract bond lattice of a graph, which is the isomorphism class of the lattice of distinct unlabelled connected partitions of a graph, suitably weighted by subgraph counting numbers. We show that these two abstract posets can be constructed from each other except in a few trivial cases. The constructions rely on certain generalisations of a lemma of Kocay in graph reconstruction theory to abstract induced subgraph posets. As a corollary, trees are reconstructible from their abstract bond lattice. We show that the chromatic symmetric function and the symmetric Tutte polynomial of a graph can be computed from its abstract induced subgraph poset. Stanley has asked if every tree is determined up to isomorphism by its chromatic symmetric function. We prove a counting lemma, and indicate future directions for a study of Stanley's question.     

Improved lower bounds on the randomized complexity of graph properties

We prove a lower bound of Ω(n^4/3 log ^1/3n) on the randomized decision tree complexity of any nontrivial monotone n‐vertex graph property, and of any nontrivial monotone bipartite graph property with bipartitions of size n. This improves the previous best bound of Ω(n^4/3) due to Hajnal (Combinatorica 11 (1991) 131–143). Our proof works by improving a graph packing lemma used in earlier work, and this improvement in turn stems from a novel probabilistic analysis. Graph packing being a well‐studied subject in its own right, our improved packing lemma and the probabilistic technique used to prove it may be of independent interest. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

代数图论中的几个新结论

本文中我们证明几个关于克希霍夫矩阵的新定理.在这些定理下,代数图论中Temperly,Kelmans,以及Fiedler提出的一些早期定理成为直接的推论.     

Szemerédi’s Lemma for the Analyst

Szemerédi’s regularity lemma is a fundamental tool in graph theory: it has many applications to extremal graph theory, graph property testing, combinatorial number theory, etc. The goal of this paper is to point out that Szemerédi’s lemma can be thought of as a result in analysis. We show three different analytic interpretations. Received: February 2006 Revision: April 2006 Accepted: April 2006     

The perturbed laplacian matrix of a graph

For a graph G, we define its perturbed Laplacian matrix as D?A(G) where A(G) is the adjacency matrix of G and D is an arbitrary diagonal matrix. Both the Laplacian matrix and the negative of the adjacency matrix are special instances of the perturbed Laplacian. Several well-known results, contained in the classical work of Fiedler and in more recent contributions of other authors are shown to be true, with suitable modifications, for the perturbed Laplacian. An appropriate generalization of the monotonicity property of a Fiedler vector for a tree is obtained. Some of the results are applied to interval graphs.     

A note on Fiedler vectors interpreted as graph realizations

The second smallest eigenvalue of the Laplace matrix of a graph and its eigenvectors, also known as Fiedler vectors in spectral graph partitioning, carry significant structural information regarding the connectivity of the graph. Using semidefinite programming duality, we offer a geometric interpretation of this eigenspace as optimal solution to a graph realization problem. A corresponding interpretation is also given for the eigenspace of the maximum eigenvalue of the Laplacian.     

On the Fiedler vectors of graphs that arise from trees by Schur complementation of the Laplacian

The utility of Fiedler vectors in interrogating the structure of graphs has generated intense interest and motivated the pursuit of further theoretical results. This paper focuses on how the Fiedler vectors of one graph reveal structure in a second graph that is related to the first. Specifically, we consider a point of articulation r in the graph G whose Laplacian matrix is L and derive a related graph G_{r} whose Laplacian is the matrix obtained by taking the Schur complement with respect to r in L. We show how Fiedler vectors of G_{r} relate to the structure of G and we provide bounds for the algebraic connectivity of G_{r} in terms of the connected components at r in G. In the case where G is a tree with points of articulation rR, we further consider the graph G_R derived from G by taking the Schur complement with respect to R in L. We show that Fiedler vectors of G_R valuate the pendent vertices of G in a manner consistent with the structure of the tree.     

Bounds on Codes Derived by Counting Components in Varshamov Graphs

We are interested in improving the Varshamov bound for finite values of length n and minimum distance d. We employ a counting lemma to this end which we find particularly useful in relation to Varshamov graphs. Since a Varshamov graph consists of components corresponding to low weight vectors in the cosets of a code it is a useful tool when trying to improve the estimates involved in the Varshamov bound. We consider how the graph can be iteratively constructed and using our observations are able to achieve a reduction in the over-counting which occurs. This tightens the lower bound for any choice of parameters n, k, d or q and is not dependent on information such as the weight distribution of a code. This work is taken from the author’s thesis [10]     

Graphs isomorphic to their maximum matching graphs

The maximum matching graph M（G） of a graph G is a simple graph whose vertices are the maximum matchings of G and where two maximum matchings are adjacent in M（G） if they differ by exactly one edge. In this paper, we prove that if a graph is isomorphic to its maximum matching graph, then every block of the graph is an odd cycle.     

与Murty-Simon猜想相关的一个重要引理的推广

一个图G的无公共邻点的点对集定义为disj(G)={(u,v):N_G(u)∩N_G(v)=Φ}.Füredi在那篇对Murty-Simon猜想取得重大进展的文章中证明了一个重要的引理:对任意具有n个顶点的图G,|E(G)|+|disj(G)|≤「n~2/2」.本文对引理中的和|E(G)|+|disj(G)|做了一些更加深入的研究并对这个引理做了一些推广.     

What is the furthest graph from a hereditary property?

For a graph property P, the edit distance of a graph G from P, denoted E_P(G), is the minimum number of edge modifications (additions or deletions) one needs to apply to G to turn it into a graph satisfying P. What is the furthest graph on n vertices from P and what is the largest possible edit distance from P? Denote this maximal distance by ed(n,P). This question is motivated by algorithmic edge‐modification problems, in which one wishes to find or approximate the value of E_P(G) given an input graph G. A monotone graph property is closed under removal of edges and vertices. Trivially, for any monotone property, the largest edit distance is attained by a complete graph. We show that this is a simple instance of a much broader phenomenon. A hereditary graph property is closed under removal of vertices. We prove that for any hereditary graph property P, a random graph with an edge density that depends on P essentially achieves the maximal distance from P, that is: ed(n,P) = E_P(G(n,p(P))) + o(n²) with high probability. The proofs combine several tools, including strengthened versions of the Szemerédi regularity lemma, properties of random graphs and probabilistic arguments. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Cores of Imprimitive Symmetric Graphs of Order a Product of Two Distinct Primes

A retract of a graph Γ is an induced subgraph Ψ of Γ such that there exists a homomorphism from Γ to Ψ whose restriction to Ψ is the identity map. A graph is a core if it has no nontrivial retracts. In general, the minimal retracts of a graph are cores and are unique up to isomorphism; they are called the core of the graph. A graph Γ is G‐symmetric if G is a subgroup of the automorphism group of Γ that is transitive on the vertex set and also transitive on the set of ordered pairs of adjacent vertices. If in addition the vertex set of Γ admits a nontrivial partition that is preserved by G, then Γ is an imprimitive G‐symmetric graph. In this paper cores of imprimitive symmetric graphs Γ of order a product of two distinct primes are studied. In many cases the core of Γ is determined completely. In other cases it is proved that either Γ is a core or its core is isomorphic to one of two graphs, and conditions on when each of these possibilities occurs is given.     

Cutting lemma and union lemma for the domination game

Two new techniques are introduced into the theory of the domination game. The cutting lemma bounds the game domination number of a partially dominated graph with the game domination number of a suitably modified partially dominated graph. The union lemma bounds the S-game domination number of a disjoint union of paths using appropriate weighting functions. Using these tools a conjecture asserting that the so-called three legged spiders are game domination critical graphs is proved. An extended cutting lemma is also derived and all game domination critical trees on 18, 19, and 20 vertices are listed.     

On the Laplacian energy of a graph

In this paper we consider the energy of a simple graph with respect to its Laplacian eigenvalues, and prove some basic properties of this energy. In particular, we find the minimal value of this energy in the class of all connected graphs on n vertices (n = 1, 2, ...). Besides, we consider the class of all connected graphs whose Laplacian energy is uniformly bounded by a constant α ⩾ 4, and completely describe this class in the case α = 40.     

On the least eigenvalue of a unicyclic mixed graph

Using the result on Fiedler vectors of a simple graph, we obtain a property on the structure of the eigenvectors of a nonsingular unicyclic mixed graph corresponding to its least eigenvalue. With the property, we get some results on minimizing and maximizing the least eigenvalue over all nonsingular unicyclic mixed graphs on n vertices with fixed girth. In particular, the graphs which minimize and maximize, respectively, the least eigenvalue are given over all such graphs with girth 3.     

On Schreier graphs of gyrogroup actions

The notion of a group action can be extended to the case of gyrogroups. In this article, we examine a digraph and graph associated with a gyrogroup action on a finite nonempty set, called a Schreier digraph and graph. We show that algebraic properties of gyrogroups and gyrogroup actions such as being gyrocommutative, being transitive, and being fixed-point-free are reflected in their Schreier digraphs and graphs. We also prove graph-theoretic versions of the three fundamental theorems involving actions: the Cauchy–Frobenius lemma (also known as the Burnside lemma), the orbit-stabilizer theorem, and the orbit decomposition theorem. Finally, we make a connection between gyrogroup actions and actions of symmetric groups by evaluation via Schreier digraphs and graphs.     

Regular bipartite graphs are antimagic

A labeling of a graph G is a bijection from E(G) to the set {1, 2,… |E(G)|}. A labeling is antimagic if for any distinct vertices u and v, the sum of the labels on edges incident to u is different from the sum of the labels on edges incident to v. We say a graph is antimagic if it has an antimagic labeling. In 1990, Hartsfield and Ringel conjectured that every connected graph other than K₂ is antimagic. In this article, we show that every regular bipartite graph (with degree at least 2) is antimagic. Our technique relies heavily on the Marriage Theorem. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 173–182, 2009     

Clique-transversal sets in 4-regular claw-free graphs

A clique-transversal set D of a graph G is a set of vertices of G such that D meets all cliques of G. The clique-transversal number, denoted by τ _c (G), is the minimum cardinality of a clique-transversal set in G. In this paper we give the exact value of the clique-transversal number for the line graph of a complete graph. Also, we give a lower bound on the clique-transversal number for 4-regular claw-free graphs and characterize the extremal graphs achieving the lower bound.     

Connections between generalized graph entropies and graph energy

Dehmer and Mowshowitz introduced a class of generalized graph entropies using known information‐theoretic measures. These measures rely on assigning a probability distribution to a graph. In this article, we prove some extremal properties of such generalized graph entropies by using the graph energy and the spectral moments. Moreover, we study the relationships between the generalized graph entropies and compute the values of the generalized graph entropies for special graph classes. © 2014 Wiley Periodicals, Inc. Complexity 21: 35–41, 2015