Steiner intervals and Steiner geodetic numbers in distance-hereditary graphs

A Steiner tree for a set S of vertices in a connected graph G is a connected subgraph of G with a smallest number of edges that contains S. The Steiner interval I(S) of S is the union of all the vertices of G that belong to some Steiner tree for S. If S={u,v}, then I(S)=I[u,v] is called the interval between u and v and consists of all vertices that lie on some shortest u-v path in G. The smallest cardinality of a set S of vertices such that ?_u,v∈SI[u,v]=V(G) is called the geodetic number and is denoted by g(G). The smallest cardinality of a set S of vertices of G such that I(S)=V(G) is called the Steiner geodetic number of G and is denoted by sg(G). We show that for distance-hereditary graphs g(G)?sg(G) but that g(G)/sg(G) can be arbitrarily large if G is not distance hereditary. An efficient algorithm for finding the Steiner interval for a set of vertices in a distance-hereditary graph is described and it is shown how contour vertices can be used in developing an efficient algorithm for finding the Steiner geodetic number of a distance-hereditary graph.     

Clique-transversal sets in 4-regular claw-free graphs

A clique-transversal set D of a graph G is a set of vertices of G such that D meets all cliques of G. The clique-transversal number, denoted by τ _c (G), is the minimum cardinality of a clique-transversal set in G. In this paper we give the exact value of the clique-transversal number for the line graph of a complete graph. Also, we give a lower bound on the clique-transversal number for 4-regular claw-free graphs and characterize the extremal graphs achieving the lower bound.     

On Clique-Transversals and Clique-Independent Sets

A clique-transversal of a graph G is a subset of vertices intersecting all the cliques of G. A clique-independent set is a subset of pairwise disjoint cliques of G. Denote by _C (G) and _C (G) the cardinalities of the minimum clique-transversal and maximum clique-independent set of G, respectively. Say that G is clique-perfect when _C (H)= _C (H), for every induced subgraph H of G. In this paper, we prove that every graph not containing a 4-wheel nor a 3-fan as induced subgraphs and such that every odd cycle of length greater than 3 has a short chord is clique-perfect. The proof leads to polynomial time algorithms for finding the parameters _C (G) and _C (G), for graphs belonging to this class. In addition, we prove that to decide whether or not a given subset of vertices of a graph is a clique-transversal is Co-NP-Complete. The complexity of this problem has been mentioned as unknown in the literature. Finally, we describe a family of highly clique-imperfect graphs, that is, a family of graphs G whose difference _C (G)– _C (G) is arbitrarily large.     

Graham’s pebbling conjecture on products of many cycles

A pebbling move on a connected graph G consists of removing two pebbles from some vertex and adding one pebble to an adjacent vertex. We define f_t(G) as the smallest number such that whenever f_t(G) pebbles are on G, we can move t pebbles to any specified, but arbitrary vertex. Graham conjectured that f₁(G×H)≤f₁(G)f₁(H) for any connected G and H. We define the α-pebbling number α(G) and prove that α(C_pj×?×C_p2×C_p1×G)≤α(C_pj)?α(C_p2)α(C_p1)α(G) when none of the cycles is C₅, and G satisfies one more criterion. We also apply this result with G=C₅×C₅ by showing that C₅×C₅ satisfies Chung’s two-pebbling property, and establishing bounds for f_t(C₅×C₅).     

Well-covered graphs and factors

A maximum independent set of vertices in a graph is a set of pairwise nonadjacent vertices of largest cardinality α. Plummer [Some covering concepts in graphs, J. Combin. Theory 8 (1970) 91-98] defined a graph to be well-covered, if every independent set is contained in a maximum independent set of G. Every well-covered graph G without isolated vertices has a perfect [1,2]-factor F_G, i.e. a spanning subgraph such that each component is 1-regular or 2-regular. Here, we characterize all well-covered graphs G satisfying α(G)=α(F_G) for some perfect [1,2]-factor F_G. This class contains all well-covered graphs G without isolated vertices of order n with α?(n-1)/2, and in particular all very well-covered graphs.     

On the chromatic number of circulant graphs

Given a set D of a cyclic group C, we study the chromatic number of the circulant graph G(C,D) whose vertex set is C, and there is an edge ij whenever i−j∈D∪−D. For a fixed set D={a,b,c:a<b<c} of positive integers, we compute the chromatic number of circulant graphs G(Z_N,D) for all N≥4bc. We also show that, if there is a total order of D such that the greatest common divisors of the initial segments form a decreasing sequence, then the chromatic number of G(Z,D) is at most 4. In particular, the chromatic number of a circulant graph on Z_N with respect to a minimum generating set D is at most 4. The results are based on the study of the so-called regular chromatic number, an easier parameter to compute. The paper also surveys known results on the chromatic number of circulant graphs.     

An upper bound on the domination number of a graph with minimum degree 2

A set S of vertices in a graph G is a dominating set of G if every vertex of V(G)?S is adjacent to some vertex in S. The minimum cardinality of a dominating set of G is the domination number of G, denoted as γ(G). Let P_n and C_n denote a path and a cycle, respectively, on n vertices. Let k₁(F) and k₂(F) denote the number of components of a graph F that are isomorphic to a graph in the family {P₃,P₄,P₅,C₅} and {P₁,P₂}, respectively. Let L be the set of vertices of G of degree more than 2, and let G−L be the graph obtained from G by deleting the vertices in L and all edges incident with L. McCuaig and Shepherd [W. McCuaig, B. Shepherd, Domination in graphs with minimum degree two, J. Graph Theory 13 (1989) 749-762] showed that if G is a connected graph of order n≥8 with δ(G)≥2, then γ(G)≤2n/5, while Reed [B.A. Reed, Paths, stars and the number three, Combin. Probab. Comput. 5 (1996) 277-295] showed that if G is a graph of order n with δ(G)≥3, then γ(G)≤3n/8. As an application of Reed’s result, we show that if G is a graph of order n≥14 with δ(G)≥2, then .     

RELATIONS AMONG SOME PARAMETERS OF HYPERGRAPHS

The relations among the dominating number, independence number and covering number of hypergraphs are investigated. Main results are as follows：Dv（H）≤min{α≤（H）, p（H）, p（H）, T（H）}; De（H）≤min{v（H）, T（H）, p（H）}; DT（H） ≤αT（H）; S（H）≤ Dv （H） ＋ α（H）≤n; 2≤ Dv （H） ＋ T（H） ≤n; 2 〈 Dv （H） ＋ v（H）≤n/2 ＋ [n/r]; Dv （H） ＋ p（H） 〈_n;2≤De（H） ＋ Dv（H）≤n/2 ＋ [n/r];α（H） ＋ De（H）≤n;2 ≤ De（H） ＋ v（H）≤2[n/r]; 2 De（H） ＋ p（H）≤n-r ＋ 2.     

The signed domatic number of some regular graphs

Let G be a finite and simple graph with vertex set V(G), and let f:V(G)→{−1,1} be a two-valued function. If ∑_x∈N[v]f(x)≥1 for each v∈V(G), where N[v] is the closed neighborhood of v, then f is a signed dominating function on G. A set {f₁,f₂,…,f_d} of signed dominating functions on G with the property that for each x∈V(G), is called a signed dominating family (of functions) on G. The maximum number of functions in a signed dominating family on G is the signed domatic number on G. In this paper, we investigate the signed domatic number of some circulant graphs and of the torus C_p×C_q.     

Triangle-free graphs whose independence number equals the degree

In a triangle-free graph, the neighbourhood of every vertex is an independent set. We investigate the class S of triangle-free graphs where the neighbourhoods of vertices are maximum independent sets. Such a graph G must be regular of degree d=α(G) and the fractional chromatic number must satisfy χ_f(G)=|G|/α(G). We indicate that S is a rich family of graphs by determining the rational numbers c for which there is a graph G∈S with χ_f(G)=c except for a small gap, where we cannot prove the full statement. The statements for c≥3 are obtained by using, modifying, and re-analysing constructions of Sidorenko, Mycielski, and Bauer, van den Heuvel and Schmeichel, while the case c<3 is settled by a recent result of Brandt and Thomassé. We will also investigate the relation between other parameters of certain graphs in S like chromatic number and toughness.     

Hamiltonicity of 4-connected graphs

Let σk（G） denote the minimum degree sum of k independent vertices in G and α（G） denote the number of the vertices of a maximum independent set of G. In this paper we prove that if G is a 4-connected graph of order n and σ5（G） 〉 n ＋ 3σ（G） ＋ 11, then G is Hamiltonian.     

The forcing hull and forcing geodetic numbers of graphs

For every pair of vertices u,v in a graph, a u-v geodesic is a shortest path from u to v. For a graph G, let I_G[u,v] denote the set of all vertices lying on a u-v geodesic. Let S⊆V(G) and I_G[S] denote the union of all I_G[u,v] for all u,v∈S. A subset S⊆V(G) is a convex set of G if I_G[S]=S. A convex hull [S]_G of S is a minimum convex set containing S. A subset S of V(G) is a hull set of G if [S]_G=V(G). The hull number h(G) of a graph G is the minimum cardinality of a hull set in G. A subset S of V(G) is a geodetic set if I_G[S]=V(G). The geodetic number g(G) of a graph G is the minimum cardinality of a geodetic set in G. A subset F⊆V(G) is called a forcing hull (or geodetic) subset of G if there exists a unique minimum hull (or geodetic) set containing F. The cardinality of a minimum forcing hull subset in G is called the forcing hull number f_h(G) of G and the cardinality of a minimum forcing geodetic subset in G is called the forcing geodetic number f_g(G) of G. In the paper, we construct some 2-connected graph G with (f_h(G),f_g(G))=(0,0),(1,0), or (0,1), and prove that, for any nonnegative integers a, b, and c with a+b≥2, there exists a 2-connected graph G with (f_h(G),f_g(G),h(G),g(G))=(a,b,a+b+c,a+2b+c) or (a,2a+b,a+b+c,2a+2b+c). These results confirm a conjecture of Chartrand and Zhang proposed in [G. Chartrand, P. Zhang, The forcing hull number of a graph, J. Combin. Math. Combin. Comput. 36 (2001) 81-94].     

A simple proof of an inequality connecting the alternating number of independent sets and the decycling number

If s_k denotes the number of independent sets of cardinality k and α(G) is the size of a maximum independent set in graph G, then I(G;x)=s₀+s₁x+?+s_α(G)x^α(G) is the independence polynomial of G (Gutman and Harary, 1983) [8].In this paper we provide an elementary proof of the inequality|I(G;−1)|≤2^φ(G) (Engström, 2009) [7], where φ(G) is the decycling number of G (Beineke and Vandell, 1997) [3], namely, the minimum number of vertices that have to be deleted in order to turn G into a forest.     

A new characterization of A 5

Let G be a group and τ _e (G) the set of numbers of elements of G of the same order. In this paper, by τ _e (G), we give a new characterization of A ₅, where A ₅ is the alternating group of degree 5. We get the theorem following: Theorem. Let G be a group, ${G\cong A_5}$ if and only if τ _e (G) = τ _e (A ₅) = {1, 15, 20, 24}.     

Signed star domatic number of a graph

Let G be a simple graph without isolated vertices with vertex set V(G) and edge set E(G). A function f:E(G)?{−1,1} is said to be a signed star dominating function on G if ∑_e∈E(v)f(e)≥1 for every vertex v of G, where E(v)={uv∈E(G)∣u∈N(v)}. A set {f₁,f₂,…,f_d} of signed star dominating functions on G with the property that for each e∈E(G), is called a signed star dominating family (of functions) on G. The maximum number of functions in a signed star dominating family on G is the signed star domatic number of G, denoted by d_SS(G).In this paper we study the properties of the signed star domatic number d_SS(G). In particular, we determine the signed domatic number of some classes of graphs.     

Graphical properties related to minimal imperfection

Say that graph G is partitionable if there exist integers α?2, ω? 2, such that |V(G)| ≡ αω + 1 and for every υ?V(G) there exist partitions of V(G)\ υ into stable sets of size α and into eliques of size ω. An immediate consequence of Lovász' characterization of perfect graphs is that every minimal imperfect graph G is partitionable with α ≡ α (G) andω ≡ ω(G).Padberg has shown that in every minimal imperfect graph G the cliques and stable sets of maximum size satisfy a series of conditions that reflect extraordinary symmetry G. Among these conditions are: the number of cliques of size ω(G) is exactly |V(G)|; the number of stable sets of size α(G) is exactly |V(G)|: every vertex of G is contained in exactly ω(G) cliques of size ω(G) and α(G) stable sets of size α(G): for every clique Q (respectively, stable set S) of maximum size there is a unique stable set S (clique O) of maximum size such that Q∩S ≡ Ø.Let C_n^k denote the graph whose vertices can be enumerated as υ₁,…,υ_n in such a way that υ₁ and υ₁ are adjacent in G if and only if i and j differ by at most k, modulo n. Chvátal has shown that Berge's Strong Perfect graph Conjecture is equivalent to the conjecture that if G is minimal imperfect with α(G) ≡ αandω(G) ≡ ω, then G has a spanning subgraph isomorphic to C_αω+1^ω. Padberg's conditions are sufficiently restrictive to suggest the possibility of establishing the Strong Perfect Graph Conjecture by proving that any graph G satisfying these conditions must contain a spanning subgraph isomorphic to C_αω+1^ω, whereα(G) ≡ αandω(G) ≡ ω. It is shown here, using only elementary linear algebra, that all partitionable graphs satisfy Padberg's conditions, as well as additional properties of the same spirit. Then examples are provided of partitionable graphs which contain no spanning subgraph isomorphic to C_αω+1^ω, whereα(G) ≡ α and ω(G) ≡ ω.     

Bounding the sum of powers of the Laplacian eigenvalues of graphs

For a non-zero real number α, let s _α (G) denote the sum of the αth power of the non-zero Laplacian eigenvalues of a graph G. In this paper, we establish a connection between s _α (G) and the first Zagreb index in which the Hölder’s inequality plays a key role. By using this result, we present a lot of bounds of s _α (G) for a connected (molecular) graph G in terms of its number of vertices (atoms) and edges (bonds). We also present other two bounds for s _α (G) in terms of connectivity and chromatic number respectively, which generalize those results of Zhou and Trinajsti? for the Kirchhoff index [B Zhou, N Trinajsti?. A note on Kirchhoff index, Chem. Phys. Lett., 2008, 455: 120–123].     

On the Heterochromatic Number of Hypergraphs Associated to Geometric Graphs and to Matroids

The heterochromatic number h _c (H) of a non-empty hypergraph H is the smallest integer k such that for every colouring of the vertices of H with exactly k colours, there is a hyperedge of H all of whose vertices have different colours. We denote by ν(H) the number of vertices of H and by τ(H) the size of the smallest set containing at least two vertices of each hyperedge of H. For a complete geometric graph G with n ≥ 3 vertices let H = H(G) be the hypergraph whose vertices are the edges of G and whose hyperedges are the edge sets of plane spanning trees of G. We prove that if G has at most one interior vertex, then h _c (H) = ν(H) ? τ(H) + 2. We also show that h _c (H) = ν(H) ? τ(H) + 2 whenever H is a hypergraph with vertex set and hyperedge set given by the ground set and the bases of a matroid, respectively.     

On the locating chromatic number of Kneser graphs

Let c be a proper k-coloring of a connected graph G and Π=(C₁,C₂,…,C_k) be an ordered partition of V(G) into the resulting color classes. For a vertex v of G, the color code of v with respect to Π is defined to be the ordered k-tuple c_Π(v):=(d(v,C₁),d(v,C₂),…,d(v,C_k)), where d(v,C_i)=min{d(v,x)|x∈C_i},1≤i≤k. If distinct vertices have distinct color codes, then c is called a locating coloring. The minimum number of colors needed in a locating coloring of G is the locating chromatic number of G, denoted by χ_L(G). In this paper, we study the locating chromatic number of Kneser graphs. First, among some other results, we show that χ_L(KG(n,2))=n−1 for all n≥5. Then, we prove that χ_L(KG(n,k))≤n−1, when n≥k². Moreover, we present some bounds for the locating chromatic number of odd graphs.     

The hull and geodetic numbers of orientations of graphs

For an oriented graph D, let I_D[u,v] denote the set of all vertices lying on a u-v geodesic or a v-u geodesic. For S⊆V(D), let I_D[S] denote the union of all I_D[u,v] for all u,v∈S. Let [S]_D denote the smallest convex set containing S. The geodetic number g(D) of an oriented graph D is the minimum cardinality of a set S with I_D[S]=V(D) and the hull number h(D) of an oriented graph D is the minimum cardinality of a set S with [S]_D=V(D). For a connected graph G, let O(G) be the set of all orientations of G, define g⁻(G)=min{g(D):D∈O(G)}, g⁺(G)=max{g(D):D∈O(G)}, h⁻(G)=min{h(D):D∈O(G)}, and h⁺(G)=max{h(D):D∈O(G)}. By the above definitions, h⁻(G)≤g⁻(G) and h⁺(G)≤g⁺(G). In the paper, we prove that g⁻(G)<h⁺(G) for a connected graph G of order at least 3, and for any nonnegative integers a and b, there exists a connected graph G such that g⁻(G)−h⁻(G)=a and g⁺(G)−h⁺(G)=b. These results answer a problem of Farrugia in [A. Farrugia, Orientable convexity, geodetic and hull numbers in graphs, Discrete Appl. Math. 148 (2005) 256-262].