A general view on computing communities

We define a community structure of a graph as a partition of the vertices into at least two sets with the property that each vertex has connections to relatively many vertices in its own set compared to any other set in the partition and refer to the sets in such a partition as communities  . We show that it is NP-hard to compute a community containing a given set of vertices. On the other hand, we show how to compute a community structure in polynomial time for any connected graph containing at least four vertices except the star graph _Sn$S_n$. Finally, we generalize our results and formally show that counterintuitive aspects are unavoidable for any definition of a community structure with a polynomial time algorithm for computing communities containing specific vertices.     

On the distance spectral radius of cacti

A cactus is a connected graph in which any two cycles have at most one common vertex. In this article, we determine the unique graph with minimal distance spectral radius in the class of all cacti with n vertices and k cycles. Also, we determine the unique graph with minimal distance spectral radius in the class of all cacti with n vertices and r pendent vertices. Moreover, we determine the class of cacti in which the maximal distance spectral radius among all cacti with n vertices and k cycles is attained.     

A lower estimate for the achromatic number of irreducible graphs

The achromatic number of a graph is the largest number of independent sets its vertex set can be split into in such a way that the union of any two of these sets is not independent. A graph is irreducible if no two vertices have the same neighborhood. The achromatic number of an irreducible graph with n vertices is shown to be $\text{≥(}\text{1}\text{2}\text{?0(1))log}\text{n?}\text{log log}\text{n,}$ while an example of Erdös shows that it need not be log n/log 2+2 for any n. The proof uses an indiscernibility argument.     

Trees with extremal numbers of maximal independent sets including the set of leaves

A subset S of vertices of a graph G is independent if no two vertices in S are adjacent. In this paper we study maximal (with respect to set inclusion) independent sets in trees including the set of leaves. In particular the smallest and the largest number of these sets among n-vertex trees are determined characterizing corresponding trees. We define a local augmentation of trees that preserves the number of maximal independent sets including the set of leaves.     

The irredundance number and maximum degree of a graph

A vertex η in a subset X of vertices of an undirected graph is redundant if its closed neighborhood is contained in the union of closed neighborhoods of vertices of X-{η}. In the context of a communications network, this means that any vertex that may receive communications from X may also be informed from X-{η}. The irredundance number ir(G) is the minimum cardinality taken over all maximal sets of vertices having no redundancies. In this note we show that ir(G) ? n/(2Δ-1) for a graph G having n vertices and maximum degree Δ.     

The backup 2-median problem on block graphs

The backup 2-median problem is a location problem to locate two facilities at vertices with the minimum expected cost where each facility may fail with a given probability. Once a facility fails, the other one takes full responsibility for the services. Here we assume that the facilities do not fail simultaneously. In this paper, we consider the backup 2-median problem on block graphs where any two edges in one block have the same length and the lengths of edges on different blocks may be different. By constructing a tree-shaped skeleton of a block graph, we devise an O（n log n q- m）-time algorithm to solve this problem where n and m are the number of vertices and edges, respectively, in the given block graph.     

The inverse inertia problem for graphs: Cut vertices, trees, and a counterexample

Let G be an undirected graph on n vertices and let S(G) be the set of all real symmetric n×n matrices whose nonzero off-diagonal entries occur in exactly the positions corresponding to the edges of G. The inverse inertia problem for G asks which inertias can be attained by a matrix in S(G). We give a complete answer to this question for trees in terms of a new family of graph parameters, the maximal disconnection numbers of a graph. We also give a formula for the inertia set of a graph with a cut vertex in terms of inertia sets of proper subgraphs. Finally, we give an example of a graph that is not inertia-balanced, which settles an open problem from the October 2006 AIM Workshop on Spectra of Families of Matrices described by Graphs, Digraphs and Sign Patterns. We also determine some restrictions on the inertia set of any graph.     

Stability in circular arc graphs

An algorithm is presented which finds a maximum stable set of a family of n arcs on a circle in O(nlogn) time given the arcs as an unordered list of their endpoints or in O(n) time if they are already sorted. If we are given only the circular arc graph without a circular arc representation for it, then a maximum stable set can be found in O(n + δe) time where n, e, and δ are the number of vertices, edges, and minimum vertex degree, respectively. Our algorithms are based on a simple neighborhood reduction theorem which allows one to reduce any circular arc graph to a special canonical form.     

On the signless Laplacian index of cacti with a given number of pendant vertices

A connected graph G is a cactus if any two of its cycles have at most one common vertex. In this article, we determine graphs with the largest signless Laplacian index among all the cacti with n vertices and k pendant vertices. As a consequence, we determine the graph with the largest signless Laplacian index among all the cacti with n vertices; we also characterize the n-vertex cacti with a perfect matching having the largest signless Laplacian index.     

Quasi-randomness and the distribution of copies of a fixed graph

We show that if a graph G has the property that all subsets of vertices of size n/4 contain the “correct” number of triangles one would expect to find in a random graph G(n, 1/2), then G behaves like a random graph, that is, it is quasi-random in the sense of Chung, Graham, and Wilson [6]. This answers positively an open problem of Simonovits and Sós [10], who showed that in order to deduce that G is quasi-random one needs to assume that all sets of vertices have the correct number of triangles. A similar improvement of [10] is also obtained for any fixed graph other than the triangle, and for any edge density other than 1/2. The proof relies on a theorem of Gottlieb [7] in algebraic combinatorics, concerning the rank of set inclusion matrices.     

Graphs with given number of cut vertices and extremal Merrifield-Simmons index

The Merrifield-Simmons index of a graph is defined as the total number of its independent sets, including the empty set. Denote by G(n,k) the set of connected graphs with n vertices and k cut vertices. In this paper, we characterize the graphs with the maximum and minimum Merrifield-Simmons index, respectively, among all graphs in G(n,k) for all possible k values.     

Extremal values of the interval number of a graph,II

It is shown that the interval number of a graph on n vertices is at most $\text{[}\text{1}\text{4}\text{(n+1)]}$, and this bound is best possible. This means that we can represent any graph on n vertices as an intersection graph in which the sets assigned to the vertices each consist of the union of at most $\text{[}\text{1}\text{4}\text{(n+1)]}$ finite closed intervals on the real line. This upper bound is attained by the complete bipartite graph K_[n/2],[n/2].     

On the generation of bicliques of a graph

An independent set of a graph is a subset of pairwise non-adjacent vertices. A complete bipartite set B is a subset of vertices admitting a bipartition B=X∪Y, such that both X and Y are independent sets, and all vertices of X are adjacent to those of Y. If both X,Y≠∅, then B is called proper. A biclique is a maximal proper complete bipartite set of a graph. When the requirement that X and Y are independent sets of G is dropped, we have a non-induced biclique. We show that it is NP-complete to test whether a subset of the vertices of a graph is part of a biclique. We propose an algorithm that generates all non-induced bicliques of a graph. In addition, we propose specialized efficient algorithms for generating the bicliques of special classes of graphs.     

The strong metric dimension of graphs and digraphs

Let G be a connected (di)graph. A vertex w is said to strongly resolve a pair u,v of vertices of G if there exists some shortest u-w path containing v or some shortest v-w path containing u. A set W of vertices is a strong resolving set for G if every pair of vertices of G is strongly resolved by some vertex of W. The smallest cardinality of a strong resolving set for G is called the strong dimension of G. It is shown that the problem of finding the strong dimension of a connected graph can be transformed to the problem of finding the vertex covering number of a graph. Moreover, it is shown that computing this invariant is NP-hard. Related invariants for directed graphs are defined and studied.     

Noncrossing Hamiltonian paths in geometric graphs

A geometric graph is a graph embedded in the plane in such a way that vertices correspond to points in general position and edges correspond to segments connecting the appropriate points. A noncrossing Hamiltonian path in a geometric graph is a Hamiltonian path which does not contain any intersecting pair of edges. In the paper, we study a problem asked by Micha Perles: determine the largest number h(n) such that when we remove any set of h(n) edges from any complete geometric graph on n vertices, the resulting graph still has a noncrossing Hamiltonian path. We prove that . We also establish several results related to special classes of geometric graphs. Let h₁(n) denote the largest number such that when we remove edges of an arbitrary complete subgraph of size at most h₁(n) from a complete geometric graph on n vertices the resulting graph still has a noncrossing Hamiltonian path. We prove that . Let h₂(n) denote the largest number such that when we remove an arbitrary star with at most h₂(n) edges from a complete geometric graph on n vertices the resulting graph still has a noncrossing Hamiltonian path. We show that h₂(n)=⌈n/2⌉-1. Further we prove that when we remove any matching from a complete geometric graph the resulting graph will have a noncrossing Hamiltonian path.     

Partition relations for denumerable ordinals

The principal result of this paper provides a nearly complete answer to the following question. For which integers k, m, n is it true that whenever we have a graph G whose set of vertices is an ordered set of order type ωⁿ, then either this graph contains a complete subgraph with k vertices or the complement of $\text{G,}\text{G}\text{?}$ contains a complete subgraph whose set of vertices has order type ω^m.     

Structure of vertex-transitive graphs

Every vertex-transitive graph has a characteristic structure. The specific details of structure of a vertex-transitive graph are closely related to the configuration of the parts of any minimum separating set of that graph. It is shown for a vertex-transitive graph G that (i) the number n of isomorphic atomic parts admitted by any minimum separating set S is unique for that G; (ii) G is then isomorphic to a disjoint union of m(≥2) copies of such a set of n atomic parts together with some additional edges joining them; (iii) any minimum separating set S of G consists of the vertex set of the union of some k(≥1) copies of the set of n atomic parts; (iv) at most one nonatomic part will be admitted in conjunction with one or more atomic parts by any minimum separating set of G.This configuration of structure extends to nonatomic parts. A vertex-transitive graph G may contain a not necessarily unique minimum separating set S which admits t(≥3) nonatomic parts. Then it is shown that (i) some (t ? 1)-set of these nonatomic parts are pairwise isomorphic; (ii) if the remaining nonatomic part is nonisomorphic to the others then it contains more vertices than the other parts; (iii) G is isomorphic to a disjoint union of d(≥2) copies of the set of q(≥t ? 1) isomorphic nonatomic parts together with some additional edges joining them; (iv) a minimum separating set S consists of the vertex set of the union of some y(≥1) copies of the set of q isomorphic nonatomic parts. For the case of t = 2 non-atomic parts admitted by a minimum separating set S, counterexamples of (iii) and (iv) are given.     

Coloring copoints of a planar point set

To a set of n points in the plane, one can associate a graph that has less than n² vertices and has the property that k-cliques in the graph correspond vertex sets of convex k-gons in the point set. We prove an upper bound of 2^k-1 on the size of a planar point set for which the graph has chromatic number k, matching the bound conjectured by Szekeres for the clique number. Constructions of Erd?s and Szekeres are shown to yield graphs that have very low chromatic number. The constructions are carried out in the context of pseudoline arrangements.     

On the remoteness function in median graphs

A profile on a graph G is any nonempty multiset whose elements are vertices from G. The corresponding remoteness function associates to each vertex x∈V(G) the sum of distances from x to the vertices in the profile. Starting from some nice and useful properties of the remoteness function in hypercubes, the remoteness function is studied in arbitrary median graphs with respect to their isometric embeddings in hypercubes. In particular, a relation between the vertices in a median graph G whose remoteness function is maximum (antimedian set of G) with the antimedian set of the host hypercube is found. While for odd profiles the antimedian set is an independent set that lies in the strict boundary of a median graph, there exist median graphs in which special even profiles yield a constant remoteness function. We characterize such median graphs in two ways: as the graphs whose periphery transversal number is 2, and as the graphs with the geodetic number equal to 2. Finally, we present an algorithm that, given a graph G on n vertices and m edges, decides in O(mlogn) time whether G is a median graph with geodetic number 2.