Total Colorings Of Degenerate Graphs

A total coloring of a graph G is a coloring of all elements of G, i.e. vertices and edges, such that no two adjacent or incident elements receive the same color. A graph G is s-degenerate for a positive integer s if G can be reduced to a trivial graph by successive removal of vertices with degree ≤s. We prove that an s-degenerate graph G has a total coloring with Δ+1 colors if the maximum degree Δ of G is sufficiently large, say Δ≥4s+3. Our proof yields an efficient algorithm to find such a total coloring. We also give a lineartime algorithm to find a total coloring of a graph G with the minimum number of colors if G is a partial k-tree, that is, the tree-width of G is bounded by a fixed integer k.     

Expansion Of Product Replacement Graphs

We establish a connection between the expansion coefficient of the product replacement graph Γ_k(G) and the minimal expansion coefficient of a Cayley graph of G with k generators. In particular, we show that the product replacement graphs Γ_k(PSL(2,p)) form an expander family, under assumption that all Cayley graphs of PSL(2,p), with at most k generators are expanders. This gives a new explanation of the outstanding performance of the product replacement algorithm and supports the speculation that all product replacement graphs are expanders [42,52].     

Fitting Height and Character Degree Graphs

Given a group G, Γ(G) is the graph whose vertices are the primes that divide the degree of some irreducible character and two vertices p and q are joined by an edge if pq divides the degree of some irreducible character of G. By a definition of Lewis, a graph Γ has bounded Fitting height if the Fitting height of any solvable group G with Γ(G)=Γ is bounded (in terms of Γ). In this note, we prove that there exists a universal constant C such that if Γ has bounded Fitting height and Γ(G)=Γ then h(G)≤C. This solves a problem raised by Lewis. Research supported by the Spanish Ministerio de Educación y Ciencia, MTM2004-06067-C02-01 and MTM2004-04665, the FEDER and Programa Ramón y Cajal.     

On the Edge-forwarding Indices of Frobenius Graphs

A G-Frobenius graph F, as defined by Fang, Li, and Praeger, is a connected orbital graph of a Frobenius group G = K × H with Frobenius kernel K and Frobenius complement H. F is also shown to be a Cayley graph, F = Cay（K, S） for K and some subset S of the group K. On the other hand, a network N with a routing function R, written as （N, R）, is an undirected graph N together with a routing R which consists of a collection of simple paths connecting every pair of vertices in the graph. The edge-forwarding index π（N） of a network （N, R）, defined by Heydemann, Meyer, and Sotteau, is a parameter to describe tile maximum load of edges of N. In this paper, we study the edge-forwarding indices of Frobenius graphs. In particular, we obtain the edge-forwarding index of a G-Frobenius graph F with rank（G） ≤ 50.     

Homomorphisms of Products of Graphs into Graphs Without Four Cycles

Given two graphs A and G, we write if there is a homomorphism of A to G and if there is no such homomorphism. The graph G is -free if, whenever both a and c are adjacent to b and d, then a = c or b = d. We will prove that if A and B are connected graphs, each containing a triangle and if G is a -free graph with and , then (here " denotes the categorical product). Received August 31, 1998/Revised April 19, 2000 RID="†" ID="†" Supported by NSERC of Canada Grant #691325.     

Bipartite Divisor Graphs for Integer Subsets

Inspired by connections described in a recent paper by Mark L. Lewis, between the common divisor graph Γ(X) and the prime vertex graph Δ(X), for a set X of positive integers, we define the bipartite divisor graph B(X), and show that many of these connections flow naturally from properties of B(X). In particular we establish links between parameters of these three graphs, such as number and diameter of components, and we characterise bipartite graphs that can arise as B(X) for some X. Also we obtain necessary and sufficient conditions, in terms of subconfigurations of B(X), for one of Γ(X) or Δ(X) to contain a complete subgraph of size 3 or 4.     

One-regular Normal Cayley Graphs on Dihedral Groups of Valency 4 or 6 with Cyclic Vertex Stabilizer

A graph G is one-regular if its automorphism group Aut（G） acts transitively and semiregularly on the arc set. A Cayley graph Cay（Г, S） is normal if Г is a normal subgroup of the full automorphism group of Cay（Г, S）. Xu, M. Y., Xu, J. （Southeast Asian Bulletin of Math., 25, 355-363 （2001）） classified one-regular Cayley graphs of valency at most 4 on finite abelian groups. Marusic, D., Pisanski, T. （Croat. Chemica Acta, 73, 969-981 （2000）） classified cubic one-regular Cayley graphs on a dihedral group, and all of such graphs turn out to be normal. In this paper, we classify the 4-valent one-regular normal Cayley graphs G on a dihedral group whose vertex stabilizers in Aut（G） are cyclic. A classification of the same kind of graphs of valency 6 is also discussed.     

Local Algorithms for the Prime Factorization of Strong Product Graphs

The practical application of graph prime factorization algorithms is limited in practice by unavoidable noise in the data. A first step towards error-tolerant “approximate” prime factorization, is the development of local approaches that cover the graph by factorizable patches and then use this information to derive global factors. We present here a local, quasi-linear algorithm for the prime factorization of “locally unrefined” graphs with respect to the strong product. To this end we introduce the backbone \mathbbB (G)\mathbb{B} (G) for a given graph G and show that the neighborhoods of the backbone vertices provide enough information to determine the global prime factors.     

On the Convexity Number of Graphs

A set of vertices S in a graph is convex if it contains all vertices which belong to shortest paths between vertices in S. The convexity number c(G) of a graph G is the maximum cardinality of a convex set of vertices which does not contain all vertices of G. We prove NP-completeness of the problem to decide for a given bipartite graph G and an integer k whether c(G) ≥ k. Furthermore, we identify natural necessary extension properties of graphs of small convexity number and study the interplay between these properties and upper bounds on the convexity number.     

Perfect Matchings in Balanced Hypergraphs – A Combinatorial Approach

Our topic is an extension of the following classical result of Hall to hypergraphs: A bipartite graph G contains a perfect matching if and only if for each independent set X of vertices, at least |X| vertices of G are adjacent to some vertex of X. Berge generalized the concept of bipartite graphs to hypergraphs by defining a hypergraph G to be balanced if each odd cycle in G has an edge containing at least three vertices of the cycle. Based on this concept, Conforti, Cornuéjols, Kapoor, and Vušković extended Hall's result by proving that a balanced hypergraph G contains a perfect matching if and only if for any disjoint sets A and B of vertices with |A| > |B|, there is an edge in G containing more vertices in A than in B (for graphs, the latter condition is equivalent to the latter one in Hall's result). Their proof is non-combinatorial and highly based on the theory of linear programming. In the present paper, we give an elementary combinatorial proof. Received April 29, 1997     

Vertex-Disjoint Triangles in Claw-Free Graphs with Minimum Degree at Least Three

. Our main result is as follows: For any integer , if G is a claw-free graph of order at least and with minimum degree at least 3, then G contains k vertex-disjoint triangles unless G is of order and G belongs to a known class of graphs. We also construct a claw-free graph with minimum degree 3 on n vertices for each such that it does not contain k vertex-disjoint triangles. We put forward a conjecture on vertex-disjoint triangles in -free graphs. Received: November 21, 1996/Revised: Revised February 19, 1998     

On a graph related to permutability in finite groups

For a finite group G we define the graph Γ(G) to be the graph whose vertices are the conjugacy classes of cyclic subgroups of G and two conjugacy classes ${\mathcal {A}, \mathcal {B}}For a finite group G we define the graph Γ(G) to be the graph whose vertices are the conjugacy classes of cyclic subgroups of G and two conjugacy classes A, B{\mathcal {A}, \mathcal {B}} are joined by an edge if for some A ? A, B ? B A{A \in \mathcal {A},\, B \in \mathcal {B}\, A} and B permute. We characterise those groups G for which Γ(G) is complete.     

Steiner Numbers in Graphs

Abstract

The Steiner distance d(S) of a set S of vertices in a connected graph G is the minimum size of a connected subgraph of G that contains S. The Steiner number s(G) of a connected graph G of order p is the smallest positive integer m for which there exists a set S of m vertices of G such that d(S) = p—1. A smallest set S of vertices of a connected graph G of order p for which d(S) = p—1 is called a Steiner spanning set of G. It is shown that every connected graph has a unique Steiner spanning set. If G is a connected graph of order p and k is an integer with 0 ≤ k ≤ p—1, then the kth Steiner number sk(G) of G is the smallest positive integer m for which there exists a set S of m vertices of G such that d(S) = k. The sequence s_o(G),s₁ (G),…,8_p-1(G) is called the Steiner sequence of G. Steiner sequences for trees are characterized.     

Connected Domination Stable Graphs Upon Edge Addition

Abstract

A set S of vertices in a graph G is a connected dominating set of G if S dominates G and the subgraph induced by S is connected. We study the graphs for which adding any edge does not change the connected domination number.     

List Coloring of Random and Pseudo-Random Graphs

choice number of a graph G is the minimum integer k such that for every assignment of a set S(v) of k colors to every vertex v of G, there is a proper coloring of G that assigns to each vertex v a color from S(v). It is shown that the choice number of the random graph G(n, p(n)) is almost surely whenever . A related result for pseudo-random graphs is proved as well. By a special case of this result, the choice number (as well as the chromatic number) of any graph on n vertices with minimum degree at least in which no two distinct vertices have more than common neighbors is at most . Received: October 13, 1997     

Packing Non-Zero A-Paths In Group-Labelled Graphs

Let G=(V,E) be an oriented graph whose edges are labelled by the elements of a group Γ and let A⊂V. An A-path is a path whose ends are both in A. The weight of a path P in G is the sum of the group values on forward oriented arcs minus the sum of the backward oriented arcs in P. (If Γ is not abelian, we sum the labels in their order along the path.) We are interested in the maximum number of vertex-disjoint A-paths each of non-zero weight. When A = V this problem is equivalent to the maximum matching problem. The general case also includes Mader's S-paths problem. We prove that for any positive integer k, either there are k vertex-disjoint A-paths each of non-zero weight, or there is a set of at most 2k −2 vertices that meets each of the non-zero A-paths. This result is obtained as a consequence of an exact min-max theorem. These results were obtained at a workshop on Structural Graph Theory at the PIMS Institute in Vancouver, Canada. This research was partially conducted during the period the first author served as a Clay Mathematics Institute Long-Term Prize Fellow.     

On the Wiener Index of Graphs

The Wiener index of a graph G is defined as W(G)=∑ _u,v d _G (u,v), where d _G (u,v) is the distance between u and v in G and the sum goes over all the pairs of vertices. In this paper, we first present the 6 graphs with the first to the sixth smallest Wiener index among all graphs with n vertices and k cut edges and containing a complete subgraph of order n−k; and then we construct a graph with its Wiener index no less than some integer among all graphs with n vertices and k cut edges.     

Equistarable Graphs and Counterexamples to Three Conjectures on Equistable Graphs

Equistable graphs are graphs admitting positive weights on vertices such that a subset of vertices is a maximal stable set if and only if it is of total weight 1. Strongly equistable graphs are graphs such that for every and every nonempty subset T of vertices that is not a maximal stable set, there exist positive vertex weights assigning weight 1 to every maximal stable set such that the total weight of T does not equal c . General partition graphs are the intersection graphs of set systems over a finite ground set U such that every maximal stable set of the graph corresponds to a partition of U . General partition graphs are exactly the graphs every edge of which is contained in a strong clique. In 1994, Mahadev, Peled, and Sun proved that every strongly equistable graph is equistable, and conjectured that the converse holds as well. In 2009, Orlin proved that every general partition graph is equistable, and conjectured that the converse holds as well. Orlin's conjecture, if true, would imply the conjecture due to Mahadev, Peled, and Sun. An “intermediate” conjecture, posed by Miklavi? and Milani? in 2011, states that every equistable graph has a strong clique. The above conjectures have been verified for several graph classes. We introduce the notion of equistarable graphs and based on it construct counterexamples to all three conjectures within the class of complements of line graphs of triangle‐free graphs. We also show that not all strongly equistable graphs are general partition.     

Hamiltonian Cycles in Almost Claw-Free Graphs

 Some known results on claw-free graphs are generalized to the larger class of almost claw-free graphs. In this paper, we prove the following two results and conjecture that every 5-connected almost claw-free graph is hamiltonian. (1). Every 2-connected almost claw-free graph G∉J on n≤ 4 δ vertices is hamiltonian, where J is the set of all graphs defined as follows: any graph G in J can be decomposed into three disjoint connected subgraphs G ₁, G ₂ and G ₃ such that E _G (G _i , G _j ) = {u _i , u _j , v _i v _j } for i≠j and i,j = 1, 2, 3 (where u _i ≠v _i ∈V(G _i ) for i = 1, 2, 3). Moreover the bound 4δ is best possible, thereby fully generalizing several previous results. (2). Every 3-connected almost claw-free graph on at most 5δ−5 vertices is hamiltonian, hereby fully generalizing the corresponding result on claw-free graphs. Received: September 21, 1998 Final version received: August 18, 1999     

Bi-complement Reducible Graphs

We introduce a new family of bipartite graphs which is the bipartite analogue of the class ofcomplement reduciblegraphs orcographs. Abi-complement reduciblegraph orbi-cographis a bipartite graphG = (W ∪ B, E) that can be reduced to single vertices by recursively bi-complementing the edge set of all connected bipartite subgraphs. Thebi-complementedgraphofGis the graph having the same vertex setW ∪ BasG, while its edge set is equal toW × B − E. The aim of this paper is to show that there exists an equivalent definition of bi-cographs by three forbidden configurations. We also propose a tree representation for this class of graphs.