Maximal planar graphs of inscribable type and diagonal flips

A theorem due to Wagner states that given two maximal planar graphs with n vertices, one can be obtained from the other by performing a finite sequence of diagonal flips. In this paper, we show a result of a similar flavour—given two maximal planar graphs of inscribable type having the same vertex set, one can be obtained from the other by performing a finite sequence of diagonal flips such that all the intermediate graphs are of inscribable type.     

Finite common coverings of pairs of regular graphs

The graph G is a covering of the graph H if there exists a (projection) map p from the vertex set of G to the vertex set of H which induces a one-to-one correspondence between the vertices adjacent to v in G and the vertices adjacent to p(v) in H, for every vertex v of G. We show that for any two finite regular graphs G and H of the same degree, there exists a finite graph K that is simultaneously a covering both of G and H. The proof uses only Hall's theorem on 1-factors in regular bipartite graphs.     

Duality of infinite graphs

Some basic results on duality of infinite graphs are established and it is proven that a block has a dual graph if and only if it is planar and any two vertices are separated by a finite edge cut. Also, the graphs having predual graphs are characterized completely and it is shown that if $\text{G}{}^1$ is a dual and predual graph of G, then G and $\text{G}{}^1$ can be represented as geometric dual graphs. The uniqueness of dual graphs is investigated, in particular, Whitney's 2-isomorphism theorem is extended to infinite graphs. Finally, infinite minimal cuts in dual graphs are studied and the characterization (in terms of planarity and separation properties) of the graphs having dual graphs satisfying conditions on the infinite cuts, as well, is included.     

On the reduced signless Laplacian spectrum of a degree maximal graph

For a (simple) graph G, the signless Laplacian of G is the matrix A(G)+D(G), where A(G) is the adjacency matrix and D(G) is the diagonal matrix of vertex degrees of G; the reduced signless Laplacian of G is the matrix Δ(G)+B(G), where B(G) is the reduced adjacency matrix of G and Δ(G) is the diagonal matrix whose diagonal entries are the common degrees for vertices belonging to the same neighborhood equivalence class of G. A graph is said to be (degree) maximal if it is connected and its degree sequence is not majorized by the degree sequence of any other connected graph. For a maximal graph, we obtain a formula for the characteristic polynomial of its reduced signless Laplacian and use the formula to derive a localization result for its reduced signless Laplacian eigenvalues, and to compare the signless Laplacian spectral radii of two well-known maximal graphs. We also obtain a necessary condition for a maximal graph to have maximal signless Laplacian spectral radius among all connected graphs with given numbers of vertices and edges.     

Sur le nombre transversal des hypergraphes uniformes

The transversal number of a given hypergraph is the cardinality of the smallest set of vertices meeting all the edges. What is the maximal possible value of the transversal number of a r-uniform hypergraph on n vertices with maximal degree p? The problem is solved here for p = 2, by using Berge's theorem on matchings.     

Polytope des independants d'un graphe serie-parallele

A graph is said to be serie-parallel if it doesn't contain an homeomorph to K₄. The aim of the paper is the demonstration of Chvatal's conjecture on the polytope of independent set of vertices in such graphs. This is done classically by using LP-duality, the algorithm for constructing the primal-dual solution having the nice property to be linear in the number of vertices.     

Bounds on the eigenvalues of graphs with cut vertices or edges

In this paper, we characterize the extremal graph having the maximal Laplacian spectral radius among the connected bipartite graphs with n vertices and k cut vertices, and describe the extremal graph having the minimal least eigenvalue of the adjacency matrices of all the connected graphs with n vertices and k cut edges. We also present lower bounds on the least eigenvalue in terms of the number of cut vertices or cut edges and upper bounds on the Laplacian spectral radius in terms of the number of cut vertices.     

Diameters of random circulant graphs

The diameter of a graph measures the maximal distance between any pair of vertices. The diameters of many small-world networks, as well as a variety of other random graph models, grow logarithmically in the number of nodes. In contrast, the worst connected networks are cycles whose diameters increase linearly in the number of nodes. In the present study we consider an intermediate class of examples: Cayley graphs of cyclic groups, also known as circulant graphs or multi-loop networks. We show that the diameter of a random circulant 2k-regular graph with n vertices scales as n ^1/k , and establish a limit theorem for the distribution of their diameters. We obtain analogous results for the distribution of the average distance and higher moments.     

Note on Halin's theorem on minimally connected graphs

In this note it is shown that any finite directed graph of strong connectivity n contains either a vertex with indegree n, a vertex with outdegree n, or an edge whose removal does not decrease the connectivity. This is a directed graph counterpart of Halin's theorem on undirected graphs. It is pointed out that only a few preparations and modifications are necessary to make his proof valid for directed graphs.     

Planarity and duality of finite and infinite graphs

We present a short proof of the following theorems simultaneously: Kuratowski's theorem, Fary's theorem, and the theorem of Tutte that every 3-connected planar graph has a convex representation. We stress the importance of Kuratowski's theorem by showing how it implies a result of Tutte on planar representations with prescribed vertices on the same facial cycle as well as the planarity criteria of Whitney, MacLane, Tutte, and Fournier (in the case of Whitney's theorem and MacLane's theorem this has already been done by Tutte). In connection with Tutte's planarity criterion in terms of non-separating cycles we give a short proof of the result of Tutte that the induced non-separating cycles in a 3-connected graph generate the cycle space. We consider each of the above-mentioned planarity criteria for infinite graphs. Specifically, we prove that Tutte's condition in terms of overlap graphs is equivalent to Kuratowski's condition, we characterize completely the infinite graphs satisfying MacLane's condition and we prove that the 3-connected locally finite ones have convex representations. We investigate when an infinite graph has a dual graph and we settle this problem completely in the locally finite case. We show by examples that Tutte's criterion involving non-separating cycles has no immediate extension to infinite graphs, but we present some analogues of that criterion for special classes of infinite graphs.     

On certain spanning subgraphs of embeddings with applications to domination

We prove the existence of certain spanning subgraphs of graphs embedded in the torus and the Klein bottle. Matheson and Tarjan proved that a triangulated disc with n vertices can be dominated by a set of no more than n/3 of its vertices and thus, so can any finite graph which triangulates the plane. We use our existence theorems to prove results closely allied to those of Matheson and Tarjan, but for the torus and the Klein bottle.     

A smallest graph of girth 5 and valency 5

We give a graph of girth 5 and valency 5 having 30 vertices. It is shown that this is the minimum number of vertices. Further we construct graphs of girth 5 and valency p (p a prime ≥ 3) having 2p² ? 2p vertices.     

Theory of path length distributions I

The Path Length Distribution (PLD) of a (p, q) graph is defined to be the array (X₀, X₁, X₂, …, X_p-1), where X₀ is the number of (unordered) pairs of vertices which have no path connecting them and X_l, 1 ≦ l ≦ p-1, is the number of pairs of vertices which are connected by a path of length l (see [1, 2]). The topic of this paper is the occurence of non-isomorphic graphs having the same path length distribution. For trees, a constructive procedure is given, showing that for any positive integer N there exist N non-isomorphic trees of diameter four which have the same PLD. Also considered are PLD-maximal graphs — those graphs with p vertices such that all pairs of vertices are connected by a path of length l for 2 ≦ l ≦ p-1. In addition to providing more examples of non-isomorphic graphs having the same PLD, PLD-maximal graphs are of intrinsic interest. For PLD-maximal graphs, we give sufficient degree and edge conditions and a necessary edge condition.     

Triangle-free partial graphs and edge covering theorems

In section 1 some lower bounds are given for the maximal number of edges ofa (p ? 1)- colorable partial graph. Among others we show that a graph on n vertices with m edges has a (p?1)-colorable partial graph with at least mT_n.p/(ⁿ₂) edges, where T_n.p denotes the so called Turán number. These results are used to obtain upper bounds for special edge covering numbers of graphs. In Section 2 we prove the following theorem: If G is a simple graph and μ is the maximal cardinality of a triangle-free edge set of G, then the edges of G can be covered by μ triangles and edges. In Section 3 related questions are examined.     

Unoriented Laplacian maximizing graphs are degree maximal

A connected graph is said to be unoriented Laplacian maximizing if the spectral radius of its unoriented Laplacian matrix attains the maximum among all connected graphs with the same number of vertices and the same number of edges. A graph is said to be threshold (maximal) if its degree sequence is not majorized by the degree sequence of any other graph (and, in addition, the graph is connected). It is proved that an unoriented Laplacian maximizing graph is maximal and also that there are precisely two unoriented Laplacian maximizing graphs of a given order and with nullity 3. Our treatment depends on the following known characterization: a graph G is threshold (maximal) if and only if for every pair of vertices u,v of G, the sets N(u)?{v},N(v)?{u}, where N(u) denotes the neighbor set of u in G, are comparable with respect to the inclusion relation (and, in addition, the graph is connected). A conjecture about graphs that maximize the unoriented Laplacian matrix among all graphs with the same number of vertices and the same number of edges is also posed.     

On the Sperner lemma and some colorings of graphs

In this journal, Daniel I. A. Cohen [2] gave a proof of the strong Sperner lemma based on “search” techniques of paths. Klaus Wagner [5] associates a particular tree to a labeled subdivision of a geometric simplex and proves that lemma by counting the number of vertices with an odd degree of that tree. In this paper we prove a general theorem about colorings of simplicial complexes by using a method similar to Wagner's. This theorem implies the strong Sperner lemma and can be used to study some colorings of graphs.     

Theorems on partitioned matrices revisited and their applications to graph spectra

Some old results about spectra of partitioned matrices due to Goddard and Schneider or Haynsworth are re-proved. A new result is given for the spectrum of a block-stochastic matrix with the property that each off-diagonal block has equal entries and each diagonal block has equal diagonal entries and equal off-diagonal entries. The result is applied to the study of the spectra of the usual graph matrices by partitioning the vertex set of the graph according to the neighborhood equivalence relation. The concept of a reduced graph matrix is introduced. The question of when n-2 is the second largest signless Laplacian eigenvalue of a connected graph of order n is treated. A recent conjecture posed by Tam, Fan and Zhou on graphs that maximize the signless Laplacian spectral radius over all (not necessarily connected) graphs with given numbers of vertices and edges is refuted. The Laplacian spectrum of a (degree) maximal graph is reconsidered.     

Intervals in matroid basis graphs

An interval in a graph is a subgraph induced by all the vertices on shortest paths between two given vertices. Intervals in matroid basis graphs satisfy many nice properties. Key results are: (1) any two vertices of a basis graph are together in some longest interval; (2) every basis graph with the minimum number of vertices for its diameter is an interval, indeed a hypercube. (1) turns out to be a simple case of a theorem in Edmonds' theory of matroid partition.     

Minimum Sum Coloring of P4-sparse graphs

In this paper, we study the Minimum Sum Coloring (MSC) problem on P₄-sparse graphs. In the MSC problem, we aim to assign natural numbers to vertices of a graph such that adjacent vertices get different numbers, and the sum of the numbers assigned to the vertices is minimum. First, we introduce the concept of maximal sequence associated with an optimal solution of the MSC problem of any graph. Next, based in such maximal sequences, we show that there is a large sub-family of P₄-sparse graphs for which the MSC problem can be solved in polynomial-time.     

On a conjecture of Brouwer involving the connectivity of strongly regular graphs

In this paper, we study a conjecture of Andries E. Brouwer from 1996 regarding the minimum number of vertices of a strongly regular graph whose removal disconnects the graph into non-singleton components.We show that strongly regular graphs constructed from copolar spaces and from the more general spaces called Δ-spaces are counterexamples to Brouwer?s Conjecture. Using J.I. Hall?s characterization of finite reduced copolar spaces, we find that the triangular graphs T(m), the symplectic graphs Sp(2r,q) over the field Fq (for any q prime power), and the strongly regular graphs constructed from the hyperbolic quadrics O⁺(2r,2) and from the elliptic quadrics O⁻(2r,2) over the field F₂, respectively, are counterexamples to Brouwer?s Conjecture. For each of these graphs, we determine precisely the minimum number of vertices whose removal disconnects the graph into non-singleton components. While we are not aware of an analogue of Hall?s characterization theorem for Δ-spaces, we show that complements of the point graphs of certain finite generalized quadrangles are point graphs of Δ-spaces and thus, yield other counterexamples to Brouwer?s Conjecture.We prove that Brouwer?s Conjecture is true for many families of strongly regular graphs including the conference graphs, the generalized quadrangles GQ(q,q) graphs, the lattice graphs, the Latin square graphs, the strongly regular graphs with smallest eigenvalue −2 (except the triangular graphs) and the primitive strongly regular graphs with at most 30 vertices except for few cases.We leave as an open problem determining the best general lower bound for the minimum size of a disconnecting set of vertices of a strongly regular graph, whose removal disconnects the graph into non-singleton components.