On computing the distinguishing and distinguishing chromatic numbers of interval graphs and other results

A vertex k-coloring of graph G is distinguishing if the only automorphism of G that preserves the colors is the identity map. It is proper-distinguishing if the coloring is both proper and distinguishing. The distinguishing number ofG, D(G), is the smallest integer k so that G has a distinguishing k-coloring; the distinguishing chromatic number ofG, χ_D(G), is defined similarly.It has been shown recently that the distinguishing number of a planar graph can be determined efficiently by counting a related parameter-the number of inequivalent distinguishing colorings of the graph. In this paper, we demonstrate that the same technique can be used to compute the distinguishing number and the distinguishing chromatic number of an interval graph. We make use of PQ-trees, a classic data structure that has been used to recognize and test the isomorphism of interval graphs; our algorithms run in O(n³log³n) time for graphs with n vertices. We also prove a number of results regarding the computational complexity of determining a graph’s distinguishing chromatic number.     

On defect-d matchings in graphs

A defect-d matching in a graph G is a matching which covers all but d vertices of G. G is d-covered if each edge of G belongs to a defect-d matching. Here we characterise d-covered graphs and d-covered connected bipartite graphs. We show that a regular graph G of degree r which is (r ? 1)-edge-connected is 0-covered or 1-covered depending on whether G has an even or odd number of vertices, but, given any non-negative integers r and d, there exists a graph regular of degree r with connectivity and edge-connectivity r ? 2 which does not even have a defect-d matching. Finally, we prove that a vertex-transitive graph is 0-covered or 1-covered depending on whether it has an even or odd number of vertices.     

On dominator colorings in graphs

A dominator coloring of a graph G is a proper coloring of G in which every vertex dominates every vertex of at least one color class. The minimum number of colors required for a dominator coloring of G is called the dominator chromatic number of G and is denoted by ?? _d (G). In this paper we present several results on graphs with ?? _d (G)?=???(G) and ?? _d (G)?=???(G) where ??(G) and ??(G) denote respectively the chromatic number and the domination number of a graph G. We also prove that if ??(G) is the Mycielskian of G, then ?? _d (G)?+?1?????? _d (??(G))?????? _d (G)?+?2.     

A note on the independence number of triangle-free graphs

Let G be a triangle-free graph on n points with average degree d. Let α be the independence number of G. In this note we give a simple proof that α ? n (d ln d ? d + 1)/(d ? 1)². We also consider what happens when G contains a limited number of triangles.     

The distinguishing chromatic number of Cartesian products of two complete graphs

A labeling of a graph G is distinguishing if it is only preserved by the trivial automorphism of G. The distinguishing chromatic number of G is the smallest integer k such that G has a distinguishing labeling that is at the same time a proper vertex coloring. The distinguishing chromatic number of the Cartesian product is determined for all k and n. In most of the cases it is equal to the chromatic number, thus answering a question of Choi, Hartke and Kaul whether there are some other graphs for which this equality holds.     

Distinguishing Cartesian powers of graphs

The distinguishing number D(G) of a graph is the least integer d such that there is a d‐labeling of the vertices of G that is not preserved by any nontrivial automorphism of G. We show that the distinguishing number of the square and higher powers of a connected graph G ≠ K₂, K₃ with respect to the Cartesian product is 2. This result strengthens results of Albertson [Electron J Combin, 12 ( 1 ), #N17] on powers of prime graphs, and results of Klav?ar and Zhu [Eu J Combin, to appear]. More generally, we also prove that d(G □ H) = 2 if G and H are relatively prime and |H| ≤ |G| < 2^|H| ? |H|. Under additional conditions similar results hold for powers of graphs with respect to the strong and the direct product. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 250–260, 2006     

The distinguishing numbers of graphs on closed surfaces

A graph $G$ is said to be $d$-distinguishable if there is a labeling $c:V\left(G\right)\to \{1,2,\dots ,d\}$ such that no automorphism of $G$ other than the identity map preserves the labels of vertices given by $c$. The smallest $d$ for which $G$ is $d$-distinguishable is called the distinguishing number of $G$. We shall prove that every 4-representative triangulation on a closed surface, except the sphere, is 2-distinguishable after establishing a general theorem on the distinguishability of polyhedral graphs faithfully embedded on closed surfaces, and show that there is an upper bound for the distinguishing number of triangulations on a given closed surface, applying the re-embedding theory of triangulations.     

On an interpolation property of outerplanar graphs

Let D be an acyclic orientation of a graph G. An arc of D is said to be dependent if its reversal creates a directed cycle. Let d(D) denote the number of dependent arcs in D. Define d_min(G) (d_max(G)) to be the minimum (maximum) number of d(D) over all acyclic orientations D of G. We determine d_min(G) for an outerplanar graph G and prove that G has an acyclic orientation with exactly k dependent arcs if d_min(G)?k?d_max(G).     

Upper bounds on vertex distinguishing chromatic index of some Halin graphs

A vertex distinguishing edge coloring of a graph G is a proper edge coloring of G such that any pair of vertices has the distinct sets of colors. The minimum number of colors required for a vertex distinguishing edge coloring of a graph G is denoted by ???? _s (G). In this paper, we obtained upper bounds on the vertex distinguishing chromatic index of 3-regular Halin graphs and Halin graphs with ??(G) ?? 4, respectively.     

The Ramsey number of a graph with bounded maximum degree

The Ramsey number of a graph G is the least number t for which it is true that whenever the edges of the complete graph on t vertices are colored in an arbitrary fashion using two colors, say red and blue, then it is always the case that either the red subgraph contains G or the blue subgraph contains G. A conjecture of P. Erdös and S. Burr is settled in the affirmative by proving that for each d ≥ 1, there exists a constant c so that if G is any graph on n vertices with maximum degree d, then the Ramsey number of G is at most cn.     

Long Cycles Generate the Cycle Space of a Graph

Let G be a 2-connected graph in which the degree of every vertex is at least d. We prove that the cycles of length at least d + 1 generate the cycle space of G, unless G ≌ K_d+1 and d is odd. As a corollary, we deduce that the cycles of length at least d + 1 generate the subspace of even cycles in G. We also establish the existence of odd cycles of length at least d + 1 in the case when G is not bipartite.A second result states: if G is 2-connected with chromatic number at least k, then the cycles of length at least k generate the cycle space of G, unless G ≌ K_k and k is even. Similar corollaries follow, among them a stronger version of a theorem of Erdös and Hajnal.     

On primitive permutation groups with nontrivial global stabilizers

In the paper the distinguishing number D(G) of an arbitrary finite primitive permutation group G is determined. As a consequence, the distinguishing number D(Г) of an arbitrary finite graph Г with a vertex-primitive group of automorphisms is found.     

Distinguishing labeling of the actions of almost simple groups

Suppose Γ is a group acting on a set X, written as (Γ,X). An r-labeling f: X→{1,2, ..., r} of X is called distinguishing for (Γ,X) if for all σ∈Γ,σ≠1, there exists an element x∈X such that f(x)≠f(x ^σ ). The distinguishing number d(Γ,X) of (Γ,X) is the minimum r for which there is a distinguishing r-labeling for (Γ,X). If Γ is the automorphism group of a graph G, then d(Γ,V (G)) is denoted by d(G), and is called the distinguishing number of the graph G. The distinguishing set of Γ-actions is defined to be D*(Γ)={d(Γ,X): Γ acts on X}, and the distinguishing set of Γ-graphs is defined to be D(Γ)={d(G): Aut(G)≅Γ}. This paper determines the distinguishing set of Γ-actions and the distinguishing set of Γ-graphs for almost simple groups Γ.     

Bipartite regulation numbers

The bipartite regulation number br(G) of a bipartite graph G with maximum degree d is the minimum number of vertices required to add to G to construct a d-regular bipartite supergraph of G. It is shown that if G is a connected m-by-n bipartite graph with m ⩽ n and n − m ⩾ d − 1, then br(G) = n − m. If. however, n − m ⩽ d − 2, the br(G) = n ⇔ m + 2l for some l satisfying 0 ⩽ l ⩽ d − (n − m). Conversely, if l, k and d (>2) are integers such that 0 ⩽ l ⩽ k and 2 ⩽ k ⩽ d, then there is an connected m-by-n bipartite graph G of maximum degree d for which br(G) = n − m + 2l, for some m and n with k = d − (n −m).     

Lower bounds on the independence number in terms of the degrees

Wei discovered that the independence number of a graph G is at least Σ_v(1 + d(v))^?1. It is proved here that if G is a connected triangle-free graph on n ≥ 3 vertices and if G is neither an odd cycle nor an odd path, then the bound above can be increased by $\text{n}\text{Δ(Δ + 1)}$, where Δ is the maximum degree. This new bound is sharp for even cycles and for three other graphs. These results relate nicely to some algorithms for finding large independent sets. They also have a natural matrix theory interpretation. A survey of other known lower bounds on the independence number is presented.     

The basis number of the Cartesian product of stars and wheels with different ladders

The basis number of a graph G is defined to be the least positive integer d such that G has a d-fold basis for the cycle space of G. We investigate the basis number of the cartesian product of stars and wheels with ladders, circular ladders and Möbius ladders.     

Upper Bound on the Diameter of a Domination Dot-Critical Graph

A vertex of a graph is called critical if its deletion decreases the domination number, and an edge is called dot-critical if its contraction decreases the domination number. A graph is said to be dot-critical if all of its edges are dot-critical. In this paper, we show that if G is a connected dot-critical graph with domination number k??? 3 and diameter d and if G has no critical vertices, then d??? 2k?3.     

The neighborhood complex of a random graph

For a graph G, the neighborhood complex N[G] is the simplicial complex having all subsets of vertices with a common neighbor as its faces. It is a well-known result of Lovász that if ‖N[G]‖ is k-connected, then the chromatic number of G is at least k+3.We prove that the connectivity of the neighborhood complex of a random graph is tightly concentrated, almost always between 1/2 and 2/3 of the expected clique number. We also show that the number of dimensions of nontrivial homology is almost always small, O(logd), compared to the expected dimension d of the complex itself.     

The smallest Randić index for trees

The general Randi? index R _α (G) is the sum of the weight d(u)d(v) ^α over all edges uv of a graph G, where α is a real number and d(u) is the degree of the vertex u of G. In this paper, for any real number α?≠?0, the first three minimum general Randi? indices among trees are determined, and the corresponding extremal trees are characterized.     

Graphs Having (2 mod d)-Cycles

It is known that if G is a graph with minimum degree δ at least d+1, then G has a cycle of length 2 mod d. We show that if G is also bipartite, then G has a cycle of length 2 mod 2d. Both these bounds are tight in terms of minimum degree. However, we show that if G is a graph with δ ≥ d and had neither K_d nor K_d,d as an induced subgraph, then G has a cycle of length 2 mod d. If G is also bipartite, then G has a cycle of length 2 mod 2d. If G is a 2-connected graph with δ ≥ d and is not congruent to K_d nor K_d,d' (for d' ≥ d) then G has a cycle of length 2 mod d. If G is also bipartite, then G has a cycle of length 2 mod 2d.