Tutte uniqueness of line graphs

We prove that if a graph H has the same Tutte polynomial as the line graph of a d-regular, d-edge-connected graph, then H is the line graph of a d-regular graph. Using this result, we prove that the line graph of a regular complete t-partite graph is uniquely determined by its Tutte polynomial. We prove the same result for the line graph of any complete bipartite graph.     

Efficient Pattern Matching on Graph Patterns of Bounded Treewidth

This paper deals with a problem to decide whether a given graph structure appears as a pattern in the structure of a given graph. A graph pattern is a connected graph with structured variables. A variable is an ordered list of vertices that can be replaced with a connected graph by a kind of hyperedge replacements. The graph pattern matching problem (GPMP) is the computational problem to decide whether a given graph pattern matches a given graph. In this paper, we show that GPMP is solvable in polynomial time if for a given graph pattern p, the lengths of all variables of p are 2 and the base graph of p is of bounded treewidth.     

Self-clique Helly circular-arc graphs

A clique in a graph is a complete subgraph maximal under inclusion. The clique graph of a graph is the intersection graph of its cliques. A graph is self-clique when it is isomorphic to its clique graph. A circular-arc graph is the intersection graph of a family of arcs of a circle. A Helly circular-arc graph is a circular-arc graph admitting a model whose arcs satisfy the Helly property. In this note, we describe all the self-clique Helly circular-arc graphs.     

A non-factorial algorithm for canonical numbering of a graph

A graph certificate or canonical form is a short unique (up to isomorphism) representation of the graph. Thus two graphs are isomorphic iff their certificates are identical. In this paper an O(cⁿ) graph isomorphism algorithm which also yields a certificate of the graph is presented. The certificate produced by this algorithm is a canonical numbering of the vertices of the graph.     

Maximal independent sets in caterpillar graphs

A caterpillar graph is a tree in which the removal of all pendant vertices results in a chordless path. In this work, we determine the number of maximal independent sets (mis) in caterpillar graphs. For a general graph, this problem is #P—complete. We provide a polynomial time algorithm to generate the whole family of mis in a caterpillar graph. We also characterize the independent graph (intersection graph of mis) and the clique graph (intersection graph of cliques) of complete caterpillar graphs.     

The intersection graphs of subtrees in trees are exactly the chordal graphs

The intersection graph of a family of subtrees in an undirected tree is called a subtree graph. A graph is called chordal if every simple circuit with more than three vertices has an edge connecting two non-consecutive vertices. In this paper, we prove that, for a graph G, the following conditions are equivalent: (i) G is a chordal graph; (ii) G is a subtree graph; (iii) G is a proper subtree graph.Consider a chordal graph G. We give an efficient algorithm for constructing a representation of G by a family of subtrees in a tree.     

Some topological properties of star graphs: The surface area and volume

The star graph, as an interesting network topology, has been extensively studied in the past. In this paper, we address some of the combinatorial properties of the star graph. In particular, we consider the problem of calculating the surface area and volume of the star graph, and thus answering an open problem previously posed in the literature. The surface area of a sphere with radius i in a graph is the number of nodes in the graph whose distance from a given node is exactly i. The volume of a sphere with radius i in a graph is the number of nodes within distance i from the given node. In this paper, we derive explicit expressions to calculate the surface area and volume in the star graph.     

Covering the vertex set of a graph with subgraphs of smaller degree

The problem of covering the vertex set of a graph with subsets spanning subgraphs of smaller degree is studied. The result of this study is applied to give a new bound on the chromatic number of a graph in terms of the maximum vertex-degree of the graph and the maximum number of vertices in a clique of the graph. By using this bound, it is shown that if d is at least 7 and e is at least 4, then there is no regular graph of valency d, chromatic number d, whose smallest circuit has at least e edges; this settles a conjecture of Branko Grünbaum.     

The inertia of unicyclic graphs and the implications for closed-shells

The inertia of a graph is an integer triple specifying the number of negative, zero, and positive eigenvalues of the adjacency matrix of the graph. A unicyclic graph is a simple connected graph with an equal number of vertices and edges. This paper characterizes the inertia of a unicyclic graph in terms of maximum matchings and gives a linear-time algorithm for computing it. Chemists are interested in whether the molecular graph of an unsaturated hydrocarbon is (properly) closed-shell, having exactly half of its eigenvalues greater than zero, because this designates a stable electron configuration. The inertia determines whether a graph is closed-shell, and hence the reported result gives a linear-time algorithm for determining this for unicyclic graphs.     

On hereditary clique-Helly self-clique graphs

A graph is clique-Helly if any family of mutually intersecting (maximal) cliques has non-empty intersection, and it is hereditary clique-Helly (HCH) if its induced subgraphs are clique-Helly. The clique graph of a graph G is the intersection graph of its cliques, and G is self-clique if it is connected and isomorphic to its clique graph. We show that every HCH graph is an induced subgraph of a self-clique HCH graph, and give a characterization of self-clique HCH graphs in terms of their constructibility starting from certain digraphs with some forbidden subdigraphs. We also specialize this results to involutive HCH graphs, i.e. self-clique HCH graphs whose vertex-clique bipartite graph admits a part-switching involution.     

The competition number of a graph and the dimension of its hole space

The competition graph of a digraph D is a (simple undirected) graph which has the same vertex set as D and has an edge between x and y if and only if there exists a vertex v in D such that (x,v) and (y,v) are arcs of D. For any graph G, G together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number k(G) of G is the smallest number of such isolated vertices. In general, it is hard to compute the competition number k(G) for a graph G and it has been one of the important research problems in the study of competition graphs to characterize a graph by its competition number. Recently, the relationship between the competition number and the number of holes of a graph has been studied. A hole of a graph is a cycle of length at least 4 as an induced subgraph. In this paper, we conjecture that the dimension of the hole space of a graph is not smaller than the competition number of the graph. We verify this conjecture for various kinds of graphs and show that our conjectured inequality is indeed an equality for connected triangle-free graphs.     

Characterization of reducible hexagons and fast decomposition of elementary benzenoid graphs

A benzenoid graph is a finite connected plane graph with no cut vertices in which every interior region is bounded by a regular hexagon of a side length one. A benzenoid graph G is elementary if every edge belongs to a 1-factor of G. A hexagon h of an elementary benzenoid graph is reducible, if the removal of boundary edges and vertices of h results in an elementary benzenoid graph. We characterize the reducible hexagons of an elementary benzenoid graph. The characterization is the basis for an algorithm which finds the sequence of reducible hexagons that decompose a graph of this class in O(n²) time. Moreover, we present an algorithm which decomposes an elementary benzenoid graph with at most one pericondensed component in linear time.     

Combinatorial properties of boundary NLC graph languages

Node label controlled (NLC) grammars are graph grammars (operating on node labeled undirected graphs)which rewrite single nodes only and establish connections between the embedded graph and the neighbors of the rewritten node on the basis of the labels of the involved nodes only. They define (possibly infinite) languages of undirected node labeled graphs (or, if we just omit the labels, languages of unlabeled graphs). Boundary NLC (BNLC) grammars are NLC grammars with the property that whenever - in a graph already generated - two nodes may be rewritten, then these nodes are not adjacent. The graph languages generated by this type of grammars are called BNLC languages.In this paper we investigate the behaviour of graph invariants within BNLC languages. First we demonstrate that there is a dependency between the chromatic number and the clique number of graphs in BNLC languages (while this is wellknown not to be true for arbitrary graph languages). Secondly, we introduce a new graph invariant, the so-called index of a graph which seems to be very suitable for describing the adjacency structure of a graph. Then we prove that every BNLC language is of bounded index (which is shown not to be true for arbitrary graph languages). Thus we exhibit properties (concerning graph invariants) of BNLC languages which are intrinsic to this class. We use them to demonstrate that certain graph languages are not BNLC languages.     

On CCE graphs of doubly partial orders

Let D be a digraph. The competition-common enemy graph (CCE graph) of D has the same set of vertices as D and an edge between vertices u and v if and only if there are vertices w and x in D such that (w,u), (w,v), (u,x), and (v,x) are arcs of D. We call a graph a CCE graph if it is the CCE graph of some digraph. In this paper, we show that if the CCE graph of a doubly partial order does not contain C₄ as an induced subgraph, it is an interval graph. We also show that any interval graph together with enough isolated vertices is the CCE graph of some doubly partial order.     

The non-nilpotent graph of a semigroup

We associate a graph ${\mathcal{N}}_{S}$ with a semigroup S (called the upper non-nilpotent graph of S). The vertices of this graph are the elements of S and two vertices are adjacent if they generate a semigroup that is not nilpotent (in the sense of Malcev). In case S is a group this graph has been introduced by A. Abdollahi and M.?Zarrin and some remarkable properties have been proved. The aim of this paper is to study this graph (and some related graphs, such as the non-commuting graph) and to discover the algebraic structure of S determined by the associated graph. It is shown that if a finite semigroup S has empty upper non-nilpotent graph then S is positively Engel. On the other hand, a semigroup has a complete upper non-nilpotent graph if and only if it is a completely simple semigroup that is a band. One of the main results states that if all connected ${\mathcal{N}}_{S}$ -components of a semigroup S are complete (with at least two elements) then S is a band that is a semilattice of its connected components and, moreover, S is an iterated total ideal extension of its connected components. We also show that some graphs, such as a cycle C _n on n vertices (with n??5), are not the upper non-nilpotent graph of a semigroup. Also, there is precisely one graph on 4 vertices that is not the upper non-nilpotent graph of a semigroup with 4 elements. This work also is a continuation of earlier work by Okni??ski, Riley and the first named author on (Malcev) nilpotent semigroups.     

Orientable imbedding of line graphs

In this paper we compute the orientable genus of the line graph of a graph G, when G is a tree and a 2-edge connected graph, all the vertices of which have their degrees equal to 2, 3, 6, or 11 modulo 12, and either G can be imbedded with triangular faces only or G is a bipartite graph which can be imbedded with squares only as faces. In the other cases, we give an upper bound of the genus of line graphs. In this way, we solve the question of the Hamiltonian genus of the complete graph K_n, for every n ≥ 3.     

Minimal comparability completions of arbitrary graphs

A transitive orientation of an undirected graph is an assignment of directions to its edges so that these directed edges represent a transitive relation between the vertices of the graph. Not every graph has a transitive orientation, but every graph can be turned into a graph that has a transitive orientation, by adding edges. We study the problem of adding an inclusion minimal set of edges to an arbitrary graph so that the resulting graph is transitively orientable. We show that this problem can be solved in polynomial time, and we give a surprisingly simple algorithm for it. We use a vertex incremental approach in this algorithm, and we also give a more general result that describes graph classes Π for which Π completion of arbitrary graphs can be achieved through such a vertex incremental approach.     

Eulerian detachments with local edge-connectivity

For a graph G, a detachment operation at a vertex transforms the graph into a new graph by splitting the vertex into several vertices in such a way that the original graph can be obtained by contracting all the split vertices into a single vertex. A graph obtained from a given graph G by applying detachment operations at several vertices is called a detachment of graph G. While detachment operations may decrease the connectivity of graphs, there are several works on conditions for preserving the connectivity. In this paper, we present necessary and sufficient conditions for a given graph/digraph to have an Eulerian detachment that satisfies a given local edge-connectivity requirement. We also discuss conditions for the detachment to be loopless.     

The contractible subgraph of 5-connected graphs

An edge e of a k-connected graph G is said to be k-removable if G — e is still k-connected. A subgraph H of a k-connected graph is said to be k-contractible if its contraction results still in a k-connected graph. A k-connected graph with neither removable edge nor contractible subgraph is said to be minor minimally k-connected. In this paper, we show that there is a contractible subgraph in a 5-connected graph which contains a vertex who is not contained in any triangles. Hence, every vertex of minor minimally 5-connected graph is contained in some triangle.     

Fast parallel strong orientation of mixed graphs and related augmentation problems

The strong orientation problem is: Given an undirected graph, G, assign orientations to its edges so that the resulting directed graph is strongly connected. Robbins showed when such an orientation exists. A generalization of this problem is when the input graph is mixed (i.e., contains some directed and some undirected edges). Boesch and Tindell gave necessary and sufficient conditions for a strong orientation to exist in a mixed graph. In this paper we give an NC algorithm for constructing a strong orientation for a given mixed graph after determining if it exists. We also give an NC algorithm for adding a minimum set of arcs to a mixed graph to make it strongly orientable. We give simplified NC algorithms for the following special cases: find minimum augmentations to make a digraph strongly connected and to make an undirected graph bridge-connected. All the algorithms presented run within the time and processor bounds required for computing the transitive closure of a digraph.