Antipodal covering graphs

A graph $\text{Γ}$ of valency k with a group G of automorphisms may be studied via the action of G on the vertex set $\text{V}\text{Γ}$. If G acts transitively on $\text{V}\text{Γ}$, then the notions of primitivity and imprimitivity are meaningful. We consider a natural notion of “block system” for a general graph $\text{Γ}$, which allows us to derive a “quotient” graph Γ whose vertices correspond to the blocks. The ideas are applied to antipodal systems in antipodal graphs: in particular we prove that for an antipodal distance-regular graph, the block size r cannot exceed the valency k; we further show that an antipodal distance-regular graph with r = k is (i) a circuit graph, (ii) a complete bipartite graph, or (iii) a threefold covering of Tutte's trivalent eight-cage.     

On the connectivity of bipartite distance-balanced graphs

A connected graph Γ is said to be distance-balanced whenever for any pair of adjacent vertices u,v of Γ the number of vertices closer to u than to v is equal to the number of vertices closer to v than to u. In [K. Handa, Bipartite graphs with balanced (a,b)-partitions, Ars Combin.51 (1999), 113-119] Handa asked whether every bipartite distance-balanced graph, that is not a cycle, is 3-connected. In this paper the Handa question is answered in the negative. Moreover, we show that a minimal bipartite distance-balanced graph, that is not a cycle and is not 3-connected, has 18 vertices and is unique. In addition, we give a complete classification of non-3-connected bipartite distance-balanced graphs for which the minimal distance between two vertices in a 2-cut is three. All such graphs are regular and for each k≥3 there exists an infinite family of such graphs which are k-regular.Furthermore, we determine a number of structural properties that a bipartite distance-balanced graph, which is not 3-connected, must have. As an application, we give a positive answer to the Handa question for the subfamily of bipartite strongly distance-balanced graphs.     

On the maximum cardinality search lower bound for treewidth

The Maximum Cardinality Search (MCS) algorithm visits the vertices of a graph in some order, such that at each step, an unvisited vertex that has the largest number of visited neighbours becomes visited. A maximum cardinality search ordering (MCS-ordering) of a graph is an ordering of the vertices that can be generated by the MCS algorithm. The visited degree of a vertex v in an MCS-ordering is the number of neighbours of v that are before v in the ordering. The visited degree of an MCS-ordering ψ of G is the maximum visited degree over all vertices v in ψ. The maximum visited degree over all MCS-orderings of graph G is called its maximum visited degree. Lucena [A new lower bound for tree-width using maximum cardinality search, SIAM J. Discrete Math. 16 (2003) 345-353] showed that the treewidth of a graph G is at least its maximum visited degree.We show that the maximum visited degree is of size O(logn) for planar graphs, and give examples of planar graphs G with maximum visited degree k with O(k!) vertices, for all k∈N. Given a graph G, it is NP-complete to determine if its maximum visited degree is at least k, for any fixed k?7. Also, this problem does not have a polynomial time approximation algorithm with constant ratio, unless P=NP. Variants of the problem are also shown to be NP-complete.In this paper, we also propose some heuristics for the problem, and report on an experimental analysis of them. Several tiebreakers for the MCS algorithm are proposed and evaluated. We also give heuristics that give upper bounds on the value of the maximum visited degree of a graph, which appear to give results close to optimal on many graphs from real life applications.     

On bipartite distance-regular graphs with a strongly closed subgraph of diameter three

Let Γ denote a distance-regular graph with a strongly closed regular subgraph Y. Hosoya and Suzuki [R. Hosoya, H. Suzuki, Tight distance-regular graphs with respect to subsets, European J. Combin. 28 (2007) 61-74] showed an inequality for the second largest and least eigenvalues of Γ in the case Y is of diameter 2. In this paper, we study the case when Γ is bipartite and Y is of diameter 3, and obtain an inequality for the second largest eigenvalue of Γ. Moreover, we characterize the distance-regular graphs with a completely regular strongly closed subgraph H(3,2).     

Some remarks on the geodetic number of a graph

A set of vertices D of a graph G is geodetic if every vertex of G lies on a shortest path between two not necessarily distinct vertices in D. The geodetic number of G is the minimum cardinality of a geodetic set of G.We prove that it is NP-complete to decide for a given chordal or chordal bipartite graph G and a given integer k whether G has a geodetic set of cardinality at most k. Furthermore, we prove an upper bound on the geodetic number of graphs without short cycles and study the geodetic number of cographs, split graphs, and unit interval graphs.     

F-Sets in graphs

A subset S of the vertex set of a graph G is called an F-set if every α?Γ(G), the automorphism group of G, is completely specified by specifying the images under α of all the points of S, and S has a minimum number of points. The number of points, k(G), in an F-set is an invariant of G, whose properties are studied in this paper. For a finite group Γ we define k(Γ) = max{k(G) | Γ(G) = Γ}. Graphs with a given Abelian group and given k-value (k ≤ k(Γ)) have been constructed. Graphs with a given group and k-value 1 are constructed which give simple proofs to the theorems of Frucht and Bouwer on the existence of graphs with given abstract/permutation groups.     

On matching and total domination in graphs

A set M of edges of a graph G is a matching if no two edges in M are incident to the same vertex. A set S of vertices in G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The matching number is the maximum cardinality of a matching of G, while the total domination number of G is the minimum cardinality of a total dominating set of G. In this paper, we investigate the relationships between the matching and total domination number of a graph. We observe that the total domination number of every claw-free graph with minimum degree at least three is bounded above by its matching number, and we show that every k-regular graph with k?3 has total domination number at most its matching number. In general, we show that no minimum degree is sufficient to guarantee that the matching number and total domination number are comparable.     

Contraction obstructions for treewidth

We provide two parameterized graphs Γk, Πk with the following property: for every positive integer k, there is a constant ck such that every graph G with treewidth at least ck, contains one of Kk, Γk, Πk as a contraction, where Kk is a complete graph on k vertices. These three parameterized graphs can be seen as “obstruction patterns” for the treewidth with respect to the contraction partial ordering. We also present some refinements of this result along with their algorithmic consequences.     

On the global offensive alliance number of a graph

An offensive alliance in a graph Γ=(V,E) is a set of vertices S⊂V where for each vertex v in its boundary the majority of vertices in v’s closed neighborhood are in S. In the case of strong offensive alliance, strict majority is required. An alliance S is called global if it affects every vertex in V?S, that is, S is a dominating set of Γ. The global offensive alliance numberγ_o(Γ) is the minimum cardinality of a global offensive alliance in Γ. An offensive alliance is connected if its induced subgraph is connected. The global-connected offensive alliance number, γ_co(Γ), is the minimum cardinality of a global-connected offensive alliance in Γ.In this paper we obtain several tight bounds on γ_o(Γ) and γ_co(Γ) in terms of several parameters of Γ. The case of strong alliances is studied by analogy.     

Edge-distance-regular graphs

Edge-distance-regularity is a concept recently introduced by the authors which is similar to that of distance-regularity, but now the graph is seen from each of its edges instead of from its vertices. More precisely, a graph Γ with adjacency matrix A is edge-distance-regular when it is distance-regular around each of its edges and with the same intersection numbers for any edge taken as a root. In this paper we study this concept, give some of its properties, such as the regularity of Γ, and derive some characterizations. In particular, it is shown that a graph is edge-distance-regular if and only if its k-incidence matrix is a polynomial of degree k in A multiplied by the (standard) incidence matrix. Also, the analogue of the spectral excess theorem for distance-regular graphs is proved, so giving a quasi-spectral characterization of edge-distance-regularity. Finally, it is shown that every nonbipartite graph which is both distance-regular and edge-distance-regular is a generalized odd graph.     

The satisfactory partition problem

The SATISFACTORY PARTITION problem consists in deciding if a given graph has a partition of its vertex set into two nonempty parts such that each vertex has at least as many neighbors in its part as in the other part. This problem was introduced by Gerber and Kobler [Partitioning a graph to satisfy all vertices, Technical report, Swiss Federal Institute of Technology, Lausanne, 1998; Algorithmic approach to the satisfactory graph partitioning problem, European J. Oper. Res. 125 (2000) 283-291] and further studied by other authors but its complexity remained open until now. We prove in this paper that SATISFACTORY PARTITION, as well as a variant where the parts are required to be of the same cardinality, are NP-complete. However, for graphs with maximum degree at most 4 the problem is polynomially solvable. We also study generalizations and variants of this problem where a partition into k nonempty parts (k?3) is requested.     

The Erd?s-Pósa property for vertex- and edge-disjoint odd cycles in graphs on orientable surfaces

We prove that for any orientable surface S and any non-negative integer k, there exists an integer f_S(k) such that every graph G embeddable in S has either k vertex-disjoint odd cycles or a vertex set A of cardinality at most f_S(k) such that G-A is bipartite. Such a property is called the Erd?s-Pósa property for odd cycles. We also show its edge version. As Reed [Mangoes and blueberries, Combinatorica 19 (1999) 267-296] pointed out, the Erd?s-Pósa property for odd cycles do not hold for all non-orientable surfaces.     

R-domination on block graphs

The k-domination problem is to select a minimum cardinality vertex set D of a graph G such that every vertex of G is within distance k from some vertex of D. We consider a generalization of the k-domination problem, called the R-domination problem. A linear algorithm is presented that solves this problem for block graphs. Our algorithm is a generalization of Slater's algorithm [12], which is applicable for forest graphs.     

Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial k-trees

An approach for factoring general boolean functions was described in Golumbic and Mintz [Factoring logic functions using graph partitioning, in: Proceedings of IEEE/ACM International Conference on Computer Aided Design, November 1999, pp. 195-198] and Mintz and Golumbic [Factoring Boolean functions using graph partitioning, Discrete Appl. Math. 149 (2005) 131-153] which is based on graph partitioning algorithms. In this paper, we present a very fast algorithm for recognizing and factoring read-once functions which is needed as a dedicated factoring subroutine to handle the lower levels of that factoring process. The algorithm is based on algorithms for cograph recognition and on checking normality.For non-read-once functions, we investigate their factoring based on their corresponding graph classes. In particular, we show that if a function F is normal and its corresponding graph is a partial k-tree, then F is a read 2^k function and a read 2^k formula for F can be obtained in polynomial time.     

Flows and generalized coloring theorems in graphs

An (oriented) graph H is said to be F_k(k ≥ 2) iff there exists an integer flow in H with all edge-values in $\text{[1 ? k, ?1] ? [1, k ? 1]}$. It is known that a plane 2-edge-connected graph is face-colorable with k colors (k ≥ 2) iff it is F_k; W. T. Tutte has proposed [1] to seek for extensions to general graphs of coloring results known for planar graphs through the use of the F_k property. In this direction, we prove among other results that every 2-edge-connected graph is F₈.     

Connector Families of Graphs

For every pair of fixed natural numbers k > l we consider families of subgraphs of the complete graph K _n such that each graph in the family has at least k connected components while the union of any two has at most l. We show that the cardinality of such a family is at most exponential in n and determine the exact exponential growth of the largest such families for every value of k and l = 1.     

Characterization of the odd graphs Ok by parameters

In this note, we settle a problem of N. Biggs [4, p.80] by showing that for each k, no distance regular graph non-isomorphic to the odd graph O_k can have the same parameters as O_k. A related characterization of certain graphs associated with the Johnson scheme J(2k+1, k) is also given.     

Paths of homomorphisms from stable Kneser graphs

We denote by SG _n,k the stable Kneser graph (Schrijver graph) of stable n-subsets of a set of cardinality 2n+k. For k≡3 (mod 4) and n≥2 we show that there is a component of the χ-colouring graph of SG _n,k which is invariant under the action of the automorphism group of SG _n,k . We derive that there is a graph G with χ(G)=χ(SG _n,k ) such that the complex Hom(SG _n,k ,G) is non-empty and connected. In particular, for k≡3 (mod 4) and n≥2 the graph SG _n,k is not a test graph.     

A generalized characteristic polynomial of a graph having a semifree action

For an abelian group Γ, a formula to compute the characteristic polynomial of a Γ-graph has been obtained by Lee and Kim [Characteristic polynomials of graphs having a semi-free action, Linear algebra Appl. 307 (2005) 35-46]. As a continuation of this work, we give a computational formula for generalized characteristic polynomial of a Γ-graph when Γ is a finite group. Moreover, after showing that the reciprocal of the Bartholdi zeta function of a graph can be derived from the generalized characteristic polynomial of a graph, we compute the reciprocals of the Bartholdi zeta functions of wheels and complete bipartite graphs as an application of our formula.     

Grundy number and products of graphs

The Grundy number of a graph G, denoted by Γ(G), is the largest k such that G has a greedyk-colouring, that is a colouring with k colours obtained by applying the greedy algorithm according to some ordering of the vertices of G. In this paper, we study the Grundy number of the lexicographic and cartesian products of two graphs in terms of the Grundy numbers of these graphs.Regarding the lexicographic product, we show that Γ(G)×Γ(H)≤Γ(G[H])≤2^Γ(G)−1(Γ(H)−1)+Γ(G). In addition, we show that if G is a tree or Γ(G)=Δ(G)+1, then Γ(G[H])=Γ(G)×Γ(H). We then deduce that for every fixed c≥1, given a graph G, it is CoNP-Complete to decide if Γ(G)≤c×χ(G) and it is CoNP-Complete to decide if Γ(G)≤c×ω(G).Regarding the cartesian product, we show that there is no upper bound of Γ(G□H) as a function of Γ(G) and Γ(H). Nevertheless, we prove that Γ(G□H)≤Δ(G)⋅2^Γ(H)−1+Γ(H).