Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
New infinite family of regular edge-isoperimetric graphs
Bezrukov S., Bulatovic P., Kuzmanovski N. Theoretical Computer Science721 (C):42-53,2018.Type:Article
Date Reviewed: Aug 10 2018

An application, engineering or otherwise, often triggers the introduction of a new concept of a combinatorial nature. This leads researchers to study related theoretical and computational issues. Again, these problems are usually intractable; thus, researchers initiate studies on this problem for special classes of graphs, and investigate the design of appropriate approximation algorithms.

Following this trend, the paper deals with what is known as the edge-isoperimetric problem (EIP). Given a graph and a fixed integer m, EIP identifies a subset S of vertices of the graph such that the vertex-induced subgraph on S contains the largest number of edges. This number is denoted as IG(m), and the maximizing set S is called an optimal set. Bezrukov provides a good survey of results for this problem [1]. Not surprisingly, this problem arises in many applications, notably partitioning and embedding problems.

EIP is known to be NP-complete. This paper is concerned with optimal sets for Cartesian products of graphs. In particular, it is restricted to those cases where a total order on the vertices exists with the property that, for every m, the initial segment (of this order) of cardinality m is an optimal set. Such an order is called an optimal order.

There are graphs whose Cartesian products do not admit optimal orders. The main result of this paper establishes a class of graphs Hs,p,i, with s,p, and i defined appropriately with the property that the lexicographic orders of their Cartesian products are optimal. This class includes cliques, cliques with s partitions removed, and t-partite graphs as special cases. This result uses an earlier result: if the lexicographic order is optimal for the Cartesian product GxG of a graph G, then it is also optimal for the nth order Cartesian product of G. The special classes of graphs reported earlier for which this result holds are all regular and dense. This motivated the authors to look for regular and dense graphs G, which generalizes the earlier classes of graphs. In doing so, the authors use a numeric characteristic called a delta sequence; for all previously considered graphs, their delta sequences admit partitioning into maximum monotonic subsequences.

Section 2 presents certain properties of the delta sequences of graphs that admit optimal orders. Using these results, the paper gives a constructive procedure for generating the class of graphs Hs,p,i. After section 3 establishes certain further properties of delta sequences, section 4 presents the proof of the main result. This proof is rather involved. In fact, the paper establishes an extension, though minor, of the main result for maximizing what are called “downsets.”

The paper concludes with some remarks about the considerations that led to the investigation. It also points to a result by DeVries that establishes the optimality of lexicographic orders of certain complete graphs with Hamiltonian cycles removed [2].

The results presented are difficult to understand. Since the authors consider a very general class of graphs, it would have been more useful if they had given some examples of these graphs, which would offer insight into their nature.

Reviewer:  Krishnaiyan Thulasiraman Review #: CR146195 (1811-0584)
1) Bezrukov, S. L. Edge isoperimetric problems on graphs. In: Graph theory and combinatorial biologyBolyai Society Mathematical Studies, Vol. 7: Bolyai Society Mathematical Studies, Vol. 7. 157-197, János Bolyai Mathematical Society, 1999.
2) DeVries, J. Isoparametric problems on graphs and posets, Diploma Thesis, University of Wisconsin-Superior, 2014.
Bookmark and Share
 
Graph Theory (G.2.2 )
 
Would you recommend this review?
yes
no
Other reviews under "Graph Theory": Date
Graphs and algorithms
Gondran M., Minoux M. (ed), Vajda S., John Wiley & Sons, Inc., New York, NY, 1984. Type: Book (9789780471103745)
Jan 1 1985
On graph rewritings
Raoult J. Theoretical Computer Science 32(1-2): 1-24, 1984. Type: Article
Sep 1 1985
Non-partitionable point sets
Avis D. Information Processing Letters 19(3): 125-129, 1984. Type: Article
Jul 1 1985
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy