Generalized line graphs

Generalized line graphs extend the ideas of both line graphs and cocktail party graphs. They were originally motivated by spectral considerations. in this paper several (nonspectral) classical theorems about line graphs are extended to generalized line graphs, including the derivation and construction of the 31 minimal nongeneralized line graphs, a Krausz-type covering characterization, and Whitney-type theorems on isomorphisms and automorphisms.     

Neighbourhood-Perfect Line Graphs

We show that the line graph of any balanced hypergraph is neighbourhood-perfect. This result is a hypergraphic extension of a recent theorem in [GKLM] saying that the line graphs of bipartite graphs are neighbourhood-perfect. The note contains also a graphical extension of the same theorem: the characterization of all graphs with neighbourhood-perfect line graph. The proof relies on a characterization of neighbourhood-perfect graphs among line graphs in terms of forbidden induced subgraphs.     

Energy of generalized line graphs

The energy of a graph is equal to the sum of the absolute values of its eigenvalues. Line graphs play an important role in the study of graph theory. Generalized line graphs extend the ideas of both line graphs and cocktail party graphs. In this paper, we establish relations between the energy of the generalized line graph of a graph G and the Laplacian and signless Laplacian energies of G. We give upper and lower bounds for the energy of generalized line graphs. Finally, we present upper and lower bounds for some special graphs.     

Distance-regular Cayley graphs with least eigenvalue $$$$

We classify the distance-regular Cayley graphs with least eigenvalue \(-2\) and diameter at most three. Besides sporadic examples, these comprise of the lattice graphs, certain triangular graphs, and line graphs of incidence graphs of certain projective planes. In addition, we classify the possible connection sets for the lattice graphs and obtain some results on the structure of distance-regular Cayley line graphs of incidence graphs of generalized polygons.     

The line index and minimum cut of weighted graphs

In this paper we discuss the line index and the minimum capacity, sum of the weights in a minimum cut, of weighted graphs, relationships between the line index and the minimum capacity, between the two kinds of minimum capacities, and between graphs with only negative weights and graphs with both positive weights and negative weights. We provide linear algorithms for both the line index and the minimum capacity of series-parallel graphs. We discuss simplifications in computing the line index and the minimum capacity of weighted graphs. We show that the generalization of algorithm of Orlova and Dorfman, and Hadlock to mixed graphs is just one step. We also discuss the k-approximation of the minimum capacity.     

A characterization of partial directed line graphs

Can a directed graph be completed to a directed line graph? If possible, how many arcs must be added? In this paper we address the above questions characterizing partial directed line (PDL) graphs, i.e., partial subgraph of directed line graphs. We show that for such class of graphs a forbidden configuration criterion and a Krausz's like theorem are equivalent characterizations. Furthermore, the latter leads to a recognition algorithm that requires O(m) worst case time, where m is the number of arcs in the graph. Given a partial line digraph, our characterization allows us to find a minimum completion to a directed line graph within the same time bound.The class of PDL graphs properly contains the class of directed line graphs, characterized in [J. Blazewicz, A. Hertz, D. Kobler, D. de Werra, On some properties of DNA graphs, Discrete Appl. Math. 98(1-2) (1999) 1-19], hence our results generalize those already known for directed line graphs. In the undirected case, we show that finding a minimum line graph edge completion is NP-hard, while the problem of deciding whether or not an undirected graph is a partial graph of a simple line graph is trivial.     

Interval line graphs

We characterize the graphs whose line graphs are interval graphs.     

Square-free perfect graphs

We prove that square-free perfect graphs are bipartite graphs or line graphs of bipartite graphs or have a 2-join or a star cutset.     

A polynomial algorithm to find an independent set of maximum weight in a fork-free graph

The class of fork-free graphs is an extension of claw-free graphs and their subclass of line graphs. The first polynomial-time solution to the maximum weight independent set problem in the class of line graphs, which is equivalent to the maximum matching problem in general graphs, has been proposed by Edmonds in 1965 and then extended to the entire class of claw-free graphs by Minty in 1980. Recently, Alekseev proposed a solution for the larger class of fork-free graphs, but only for the unweighted version of the problem, i.e., finding an independent set of maximum cardinality. In the present paper, we describe the first polynomial-time algorithm to solve the problem for weighted fork-free graphs.     

On products and line graphs of signed graphs, their eigenvalues and energy

In this article we examine the adjacency and Laplacian matrices and their eigenvalues and energies of the general product (non-complete extended p-sum, or NEPS) of signed graphs. We express the adjacency matrix of the product in terms of the Kronecker matrix product and the eigenvalues and energy of the product in terms of those of the factor graphs. For the Cartesian product we characterize balance and compute expressions for the Laplacian eigenvalues and Laplacian energy. We give exact results for those signed planar, cylindrical and toroidal grids which are Cartesian products of signed paths and cycles.We also treat the eigenvalues and energy of the line graphs of signed graphs, and the Laplacian eigenvalues and Laplacian energy in the regular case, with application to the line graphs of signed grids that are Cartesian products and to the line graphs of all-positive and all-negative complete graphs.     

On minimal forbidden subgraph characterizations of balanced graphs

A graph is balanced if its clique-matrix contains no edge–vertex incidence matrix of an odd chordless cycle as a submatrix. While a forbidden induced subgraph characterization of balanced graphs is known, there is no such characterization by minimal forbidden induced subgraphs. In this work, we provide minimal forbidden induced subgraph characterizations of balanced graphs restricted to graphs that belong to one of the following graph classes: complements of bipartite graphs, line graphs of multigraphs, and complements of line graphs of multigraphs. These characterizations lead to linear-time recognition algorithms for balanced graphs within the same three graph classes.     

Graph limits and hereditary properties

We give a survey of some general results on graph limits associated to hereditary classes of graphs. As examples, we consider some classes defined by forbidden subgraphs and some classes of intersection graphs, including triangle-free graphs, chordal graphs, cographs, interval graphs, unit interval graphs, threshold graphs, and line graphs.     

Line graphs of complete multipartite graphs have small cycle double covers

It has been shown by MacGillivray and Seyffarth (Austral. J. Combin. 24 (2001) 91) that bridgeless line graphs of complete graphs, complete bipartite graphs, and planar graphs have small cycle double covers. In this paper, we extend the result for complete bipartite graphs, and show that the line graph of any complete multipartite graph (other than K_1,2) has a small cycle double cover.     

On the Zagreb indices of the line graphs of the subdivision graphs

The aim of this paper is to investigate the Zagreb indices of the line graphs of the tadpole graphs, wheel graphs and ladder graphs using the subdivision concepts.     

Rectilinear drawings of graphs

We consider graphs drawn in the plane such that every edge crosses at most one other edge. We characterize, in terms of two forbidden sub-configurations, which of these graphs are equivalent to drawings such that all edges are straight line segments. As a consequence we obtain a complete characterization of the pairs of dual graphs that can be represented as geometric dual graphs such that all edges except one are straight line segments.     

Line graphs: Their maximum nullities and zero forcing numbers

The maximum nullity over a collection of matrices associated with a graph has been attracting the attention of numerous researchers for at least three decades. Along these lines various zero forcing parameters have been devised and utilized for bounding the maximum nullity. The maximum nullity and zero forcing number, and their positive counterparts, for general families of line graphs associated with graphs possessing a variety of specific properties are analysed. Building upon earlier work, where connections to the minimum rank of line graphs were established, we verify analogous equations in the positive semidefinite cases and coincidences with the corresponding zero forcing numbers. Working beyond the case of trees, we study the zero forcing number of line graphs associated with certain families of unicyclic graphs.     

Resistance characterizations of equiarboreal graphs

A weighted (unweighted) graph $G$ is called equiarboreal if the sum of weights (the number) of spanning trees containing a given edge in $G$ is independent of the choice of edge. In this paper, we give some resistance characterizations of equiarboreal weighted and unweighted graphs, and obtain the necessary and sufficient conditions for $k$-subdivision graphs, iterated double graphs, line graphs of regular graphs and duals of planar graphs to be equiarboreal. Applying these results, we obtain new infinite families of equiarboreal graphs, including iterated double graphs of 1-walk-regular graphs, line graphs of triangle-free 2-walk-regular graphs, and duals of equiarboreal planar graphs.     

Line perfect graphs

The concept of line perfection of a graph is defined so that a simple graph is line perfect if and only if its line graph is perfect in the usual sense. Line perfect graphs are characterized as those which contain no odd cycles of size larger than 3. Two well-know theorems of König for bipartite graphs are shown to hold also for line perfect graphs; this extension provides a reinterpretation of the content of these theorems.Supported by National Science Foundation Grants GK-42095 and ENG 76-09936.     

Mock threshold graphs

Mock threshold graphs are a simple generalization of threshold graphs that, like threshold graphs, are perfect graphs. Our main theorem is a characterization of mock threshold graphs by forbidden induced subgraphs. Other theorems characterize mock threshold graphs that are claw-free and that are line graphs. We also discuss relations with chordality and well-quasi-ordering as well as algorithmic aspects.     

On finding augmenting graphs

Method of augmenting graphs is a general approach to solve the maximum independent set problem. As the problem is generally NP-hard, no polynomial time algorithms are available to implement the method. However, when restricted to particular classes of graphs, the approach may lead to efficient solutions. A famous example of this type is the maximum matching algorithm: it finds a maximum matching in a graph G, which is equivalent to finding a maximum independent set in the line graph of G. In the particular case of line graphs, the method reduces to finding augmenting (alternating) chains. Recent investigations of more general classes of graphs revealed many more types of augmenting graphs. In the present paper we study the problem of finding augmenting graphs different from chains. To simplify this problem, we introduce the notion of a redundant set. This allows us to reduce the problem to finding some basic augmenting graphs. As a result, we obtain a polynomial time solution to the maximum independent set problem in a class of graphs which extends several previously studied classes including the line graphs.