A note on generalized line graphs

Whitney's theorem on line graphs is extended to the class of generalized line graphs defined by Hoffman.     

A note on line coverings of graphs

Let minimum, maximum, refer to the number of elements in a set and let minimal, maximal refer to set inclusion. It is shown that a minimal cover of a graph is minimum if and only if it contains a maximum matching of that graph; a maximal matching of a graph is maximum if and only if it is contained in a minimum cover of that graph diminished by the set of its isolated points.     

A note on cycle spectra of line graphs

We show that line graphs G=L(H) with σ₂(G)≥7 contain cycles of all lengths k, 2rad(H)+1≤k≤c(G). This implies that every line graph of such a graph with 2rad(H)≥Δ(H) is subpancyclic, improving a recent result of Xiong and Li. The bound on σ₂(G) is best possible.     

A note on degree-continuous graphs

The minimum orders of degree-continuous graphs with prescribed degree sets were investigated by Gimbel and Zhang, Czechoslovak Math. J. 51 (126) (2001), 163–171. The minimum orders were not completely determined in some cases. In this note, the exact values of the minimum orders for these cases are obtained by giving improved upper bounds.     

A note on compact graphs

An undirected simple graph G is called compact iff its adjacency matrix A is such that the polytope S(A) of doubly stochastic matrices X which commute with A has integral-valued extremal points only. We show that the isomorphism problem for compact graphs is polynomial. Furthermore, we prove that if a graph G is compact, then a certain naive polynomial heuristic applied to G and any partner G′ decides correctly whether G and G′ are isomorphic or not. In the last section we discuss some compactness preserving operations on graphs.     

A note on assymmetric graphs

We describe a partition of the points of a graph which is related to its automorphism group. We then prove that the group of a tree is trivial if and only if this partition is the trivial one, and we formulate an algorithm which produces such a partition. Some application to graphs in general are also considered. Work supported in part by NSF Grant GP 11618.     

A note on perfect graphs

Let the lines of a complete graph be 3-colored so that no triangle gets 3 different colors. If two of these colors form perfect graphs then so does the third.     

A note on Cayley graphs

An example is given of a finite group A of order 144, with a generating set X = {x, y} such that x³ = y² = 1 and such that the Cayley graph C(A, X) has genus 4 and characteristic −6 (both of which are small relative to the order of A), although there is no short relator of the form (xy)^r with r < 12 or of the form [x, y]^r with r < 6. Accordingly this and other possible examples do not fit into a pattern suggested by [5.], 244–268).     

A note on cospectral graphs

The notion of a (1, x) adjacency matrix is introduced, together with methods for dealing with it. It is shown that in many instances this adjacency matrix is superior to the usual (0, 1) adjacency matrix, and will distinguish cospectral pairs, when the latter will not. In those cases in which the (1, x) adjacency matrix fares no better than the (0, 1) adjacency matrix, a good deal can be said about the matrices by which the cospectral pairs are similar.     

A note on Ki-perfect graphs

Ki-perfect graphs are a special instance of F - G perfect graphs, where F and G are fixed graphs with F a partial subgraph of G. Given S, a collection of G-subgraphs of graph K, an F - G cover of S is a set of T of F-subgraphs of K such that each subgraph in S contains as a subgraph a member of T. An F - G packing of S is a subcollection S′? S such that no two subgraphs in S′ have an F-subgraph in common. K is F - G perfect if for all such S, the minimum cardinality of an F - G cover of S equals the maximum cardinality of an F - G packing of S. Thus K_i-perfect graphs are precisely K_i-1 - K_i perfect graphs. We develop a hypergraph characterization of F - G perfect graphs that leads to an alternate proof of previous results on K_i-perfect graphs as well as to a characterization of F - G perfect graphs for other instances of F and G.     

A note on n-extendable graphs

A graph G having a perfect matching is called n-extendable if every matching of size n of G can be extended to a perfect matching. In this note, we show that if G is an n-extendable nonbipartite graph, then G + e is (n - 1)-extendable for any edge e ? E(G). © 1992 John Wiley & Sons, Inc.     

A note on k-cop-win graphs

The game of Cops and Robbers is a very well known game played on graphs. In this paper we will show that minimum order of a graph that needs $k$ cops to guarantee the robber’s capture is increasing in $k$.     

A note on graphs spanned by Eulerian graphs

We show that the problem raised by Boesch, Suffel, and Tindell of determining whether or not a graph is spanned by an Eulerian subgraph is NP-complete. We also note that there does exist a good algorithm for determining if a graph is spanned by a subgraph having positive even degree at every node.     

A note on graphs and sphere orders

A partially ordered set P is called a k-sphere order if one can assign to each element a ∈ P a ball B_a in R^k so that a < b iff B_a ? B_b. To a graph G = (V,E) associate a poset P(G) whose elements are the vertices and edges of G. We have v < e in P(G) exactly when v ∈ V, e ∈ E, and v is an end point of e. We show that P(G) is a 3-sphere order for any graph G. It follows from E. R. Scheinerman [“A Note on Planar Graphs and Circle Orders,” SIAM Journal of Discrete Mathematics, Vol. 4 (1991), pp. 448–451] that the least k for which G embeds in R^k equals the least k for which P(G) is a k-sphere order. For a simplicial complex K one can define P(K) by analogy to P(G) (namely, the face containment order). We prove that for each 2-dimensional simplicial complex K, there exists a k so that P(K) is a k-sphere order. © 1993 John Wiley & Sons, Inc.     

A note on maximal triangle-free graphs

We show that a maximal triangle-free graph on n vertices with minimum degree δ contains an independent set of 3δ ? n vertices which have identical neighborhoods. This yields a simple proof that if the binding number of a graph is at least 3/2 then it has a triangle. This was conjectured originally by Woodall. © 1993 John Wiley & Sons, Inc.     

A note on labeled symmetric graphs

By using the known results of groups and graphs, we determine the number of labeled symmetric graphs with a prime number of vertices.