[1] O. Favaron, A. Hansberg, and L. Volkmann. k-domination and minimum degree in graphs. J. Graph Theory, 57 no 1:33-40, 2008.
[ bib ]
A subset S of vertices of a graph G is k-dominating if every vertex not in S has at least k neighbors in S. The k-domination number γk(G) is the minimum cardinality of a k-dominating set of G. Different upper bounds on γk(G) are known in terms of the order n and the minimum degree δ of G. Cockayne, Gamble and Shepherd proved that γk(G)<= kn/(k+1) if k<= δ, and Chen and Zhou that γk(G)<= (2k-δ-1)n/(2k-δ) if (δ +3)/2<= k<= δ-1. We improve the second bound and characterize the extremal graphs for the first one. This characterization generalizes that of graphs realizing γ(G)=n/2.
[2] O. Favaron, H. Karami, and S.M. Sheikholeslami. Total domination in K5- and K6-covered graphs. Discrete Math. Theor. Comput. Science, 10:1:35-42, 2008.
[ bib ]
A graph G is Kr-covered if each vertex of G is contained in a Kr-clique. Let γt(G) denote the total domination number of G. It has been conjectured that, every Kr-covered graph of order n with no Kr-component satisfies γt(G)<= (2n)/(r+1). In this paper we prove that this conjecture is true for r=5 and 6.
[3] O. Favaron and M. A. Henning. Total domination in claw-free graphs with minimum degree two. Discrete Math., 308 (15):3213-3219, 2008.
[ bib ]
A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S (other than itself). The minimum cardinality of a total dominating set of G is the total domination number of G, denoted by γt(G). A graph is claw-free if it does not contain K1,3 as an induced subgraph. It is known (see J. Graph Theory 35 (2000), 21-45) that if G is a connected graph of order n with minimum degree at least two and G in {C3, C5, C6, C10}, then γt(G) <= 4n/7. In this paper, we show that this upper bound can be improved if G is restricted to be a claw-free graph. We show that every connected claw-free graph G of order n and minimum degree at least two satisfies γt(G) <= (n+2)/2 and we characterize those graphs for which γt(G) = (n+2)/2 .
[4] O. Favaron and M. A. Henning. Bounds on total domination in claw-free cubic graphs. Discrete Math., 308 (16):3491-3507, 2008.
[ bib ]
A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S (other than itself). The minimum cardinality of a total dominating set of G is the total domination number of G, denoted by γt(G). If G does not contain K1,3 as an induced subgraph, then G is said to be claw-free. It is shown in J. Graph Theory (46 (2004), 207-210) that if G is a graph of order n with minimum degree at least three, then γt(G) <= n/2. Two infinite families of connected cubic graphs with total domination number one-half their orders are constructed in J. Graph Theory (34 (2000), 9-19) which shows that this bound of n/2 is sharp. However every graph in these two families, except for K4 and a cubic graph of order eight, contains a claw. It is therefore a natural question to ask whether this upper bound of n/2 can be improved if we restrict G to be a connected cubic claw-free graph of order at least ten. In this paper, we answer this question in the affirmative. We prove that if G is a connected claw-free cubic graph of order n >= 10, then γt(G) <= 5n/11.
[5] O. Favaron, H. Karami, and S.M. Sheikholeslami. Total domination and total domination subdivision numbers of a graph and its complement. Discrete Math., 38 (17):4018-4023, 2008.
[ bib ]
A set S of vertices of a graph G=(V,E) with no isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γt(G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number sdγ_t(G) is the minimum number of edges that must be subdivided in order to increase the total domination number. We consider graphs of order n>= 4, minimum degree δ and maximum degree Δ. We prove that if each component of G and G has order at least 3 and G, G<> C5, then γt(G)+γt(G)<= 2n3+2 and if each component of G and G has order at least 2 and at least one component of G and G has order at least 3, then sdγ_t(G)+ sdγ_t(G)<= 2n3+2. We also give a result on γt(G)+γt(G) stronger than a conjecture by Harary and Haynes.
[6] M. Chellali, O. Favaron, T. W. Haynes, and D. Raber. Ratios of some domination parameters in trees. Discrete Math., 308 (17):3879-3887, 2008.
[ bib ]
[7] M. Blidia, M. Chellali, O. Favaron, and N. Meddah. Maximal k-independent sets in graphs. Discuss. Math. Graph Theory, 28:151-163, 2008.
[ bib ]
[8] M. Blidia, M. Chellali, and O. Favaron. Ratios of some domination parameters in graphs and claw-free graphs. In J. A. Bondy et al., editors, Graph Theory in Paris, pages 61-72. Trends Math., Birkhauser, Basel, 2007.
[ bib ]
In the class of all graphs and the class of claw-free graphs, we give exact bounds on all the ratios of two graph parameters among the domination number, the total domination number, the paired domination number, the double domination number and the independence number. We summarize the old and new results in a table and give for each bound examples of extremal families.
[9] M. Blidia, M. Chellali, O. Favaron, and N. Meddah. On k-independence in graphs with emphasis on trees. Discrete Math., 307 no 17-18:2209-2216, 2007.
[ bib ]
In a graph G=(V,E) of order n and maximum degree Δ, a subset S of vertices is a k-independent set if the subgraph induced by S has maximum degree less or equal to k-1. The lower k-independence number ik (G) is the minimum cardinality of a maximal k-independent set in G and the k-independence number βk(G) is the maximum cardinality of a k-independent set. We show that ik<= n-Δ+k-1 for any graph and any k<=Δ, and i2<= n-Δ if G is connected, that βk(T)>= kn/(k+1) for any tree, and that i2<= (n+s)/2 <= β 2 for any connected bipartite graph with s support vertices. Moreover we characterize the trees satisfying i2=n-Δ, βk= kn/(k+1), i2=(n+s)/2 or β 2=(n+s)/2.
[10] O. Favaron, H. Karami, and S.M. Sheikholeslami. Total domination and total domination subdivision numbers. Austral. J. Combin., 38:229-235, 2007.
[ bib ]
A set S of vertices of a graph G=(V,E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S.The total domination number γt(G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number sdγ_t(G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the total domination number. We show that sdγ_t(G)<= nt(G)+1 for any graph G of order n>= 3 and that sdγ_t(G)<= nt(G) except if G P3,C3,K4,P6 or C6.
[11] O. Favaron, R.C. Laskar, and D. Rautenbach. t-partitions and s-complete t-partitions of a graph. Austral. J. Combin., 36:295-302, 2006.
[ bib ]
A partition {V1,V2, ... ,Vp} of the vertex set of a graph G=(V,E) is a t-coloring, or t-partition if the number e(Vi) of edges contained in the class Vi is at most t for 1<= i<= p. The minimum number of classes in a t-coloring of G is the t-chromatic number χ t(G). For t=0, a 0-coloring is a partition of V into independent sets and χ 0(G) is the usual chromatic number χ (G). A t-coloring is s-complete if the number e(Vi,Vj) of edges between two parts Vi and Vj is at least s for all 1<= i<> j <= p. The minimum number of classes in a s-complete t-coloring of G, if any, is denoted χ ts(G). We study some properties of χ t(G) and χ ts(G), in particular some bounds on χ t(G) and some conditions for the existence of χ ts(G).
[12] O. Favaron. An alternative definition of the k-irredundance. AKCE J. Graphs Comb., 2(1):33-38, 2005.
[ bib ]
In accordance with the k-domination and the k-independence introduced by Fink and Jacobson in 1985, Jacobson, Peters and Rall defined in 1990 the concept of k-irredundance. We propose here a slightly different definition avoiding some inconveniences and keeping the main properties of the former one.
[13] O. Favaron. Bounds on total and paired domination in graphs and claw-free graphs. pages 59-73, 2005.
[ bib ]
We survey the knowns results concerning upper bounds on the parameters of domination, total domination and paired domination of a graph in terms of its order and minimum degree. These bounds are established in the class of all graphs and in the class of claw-free graphs. For two of them concerning total and paired domination in claw-free graphs, we give more details and an idea of the proofs.
[14] M. Blidia, M. Chellali, and O. Favaron. Independence and 2-domination in trees. Austral. J. Combin., 33:317-327, 2005.
[ bib ]
In a graph a vertex is said to dominate all its neighbours. A 2-dominating set of a graph G=(V,E) is a dominating set that dominates every vertex of V-S at least twice. The 2-domination number of G, which is the minimum cardinality of a 2-dominating set of G, is denoted by γ 2(G) and the independence number by β (G). We compare the value of γ 2 and β in trees and give bounds on these two parameters is terms of the order and the number of leaves of the tree. More precisely we show that for a nontrivial tree T, β (T)<= γ 2(T)<= 3β (T)/2, (n+ +2)/3<= γ 2(T) <= (n+ )/2 and β (T)<= (n+ -1)/2. We characterize the trees achieving equality in each bound.
[15] E. J. Cockayne, O. Favaron, and C. M. Mynhardt. On i--Edge-Removal-critical graphs. Discrete Math., 276(1-3):111-125, 2004.
[ bib ]
We are interested in the behaviour of the independent domination number i(G) of a graph G under edge deletion, and in particular in i--ER-critical graphs, i.e., graphs for which i(G) decreases whenever an edge e is removed. If γ (G) denotes the domination number of G, we determine all the i--ER-critical graphs G such that γ (G)=2 and i(G-e)=2 for every edge e of G. Different classes of i--ER-critical graphs such that i(G-e)>γ (G) for all or some edges e are described. Finally, for a particular family of circulants, we find the exact value of i(G-e) for every edge e of the graphs of this family and obtain as a corollary the number of automorphism classes of their edge sets.
[16] E. J. Cockayne, O. Favaron, and C. M. Mynhardt. Total domination in Kr-covered graphs. Ars Combin., 71:289-303, 2004.
[ bib ]
A graph G is Kr-covered if each vertex of G is contained in a clique Kr. Let γ(G) and γt(G) respectively denote the domination and the total domination number of G. We prove the following results for any graph G of order n:

if G is K6-covered, then γt(G)<=(n)/(3),

if G is Kr-covered with r=3 or 4 and has no component isomorphic to Kr, then γt(G)<=(2n)/(r+1),

if G is K3-covered and has no component isomorphic to K3, then γ(G)+γt(G)<=(7n)/(9).

Corollaries of the last two results are that every claw-free graph of order n and minimum degree at least 3 satisfies γt(G)<=(n)/(2) and γ(G)+γt(G)<=(7n)/(9). For general values of r, we give conjectures which would generalise the previous results. They are inspired by conjectures of Henning and Swart related to less classical parameters γK_r and γK_rt.

[17] O. Favaron, G. Fricke, W. Goddard, S. M. Hedetniemi, S. T. Hedetniemi, P. Kristiansen, R. C. Laskar, and D. Skaggs. Offensive alliances in graphs. Discuss. Math. Graph Theory, 24:263-275, 2004.
[ bib ]
A set S is an offensive alliance if for every vertex v in its boundary N(S)-S it holds that the majority of vertices in v's closed neighbourhood are in S. The offensive alliance number is the minimum cardinality of an offensive alliance. In this paper we explore the bounds on the offensive alliance and the strong offensive alliance numbers (where a strict majority is required). In particular, we show that the offensive alliance number is at most 2/3 the order and the strong offensive alliance number is at most 5/6 the order.
[18] O. Favaron, T. W. Haynes, and S. T. Hedetniemi. Domination subdivision in graphs. Utilitas Math., 66:195-209, 2004.
[ bib ]
A set S of vertices of a graph G = (V,E) is a dominating set if every vertex in V-S is adjacent to some vertex in S. The domination number γ(G) is the minimum cardinality of a dominating set of G, and the domination subdivision number sdγ(G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the domination number. In June 2000, Arumugam conjectured that 1 <= sdγ(G) <= 3 for any graph G. However, a counterexample to this conjecture suggests to the revised conjecture that 1 <= sdγ(G) <= 4 for any graph G. It is also conjectured that for every graph G with minimum degree δ(G) >= 2, sdγ(G) <= δ(G)+1. In this paper we extend several previous results and consider evidence in support of these two conjectures.
[19] O. Favaron and M. A. Henning. Paired domination in claw-free cubic graphs. Graphs Combin., 20(4):447-456, 2004.
[ bib ]
A set S of vertices in a graph G is a paired dominating set of G if every vertex of G is adjacent to some vertex in S and if the subgraph induced by S contains a perfect matching. The minimum cardinality of a paired dominating set of G is the paired domination number of G, denoted by γp(G). If G does not contain a graph F as an induced subgraph, then G is said to be F-free. In particular if F = K1,3 or K4-e, then we say that G is claw-free or diamond-free, respectively. Let G be a connected cubic graph of order n. We show that (i) if G is (K1,3, K4-e, C4)-free, then γp(G) <= 3n/8; (ii) if G is claw-free and diamond-free, then γp(G) <= 2n/5; (iii) if G is claw-free, then γp(G) <= n/2. In all three cases, the extremal graphs are characterized.
[20] O. Favaron, G. H. Fricke, D. Pritikin, and J. Puech. Irredundance and domination in kings graphs. Discrete Math., 262(1-3):131-147, 2003.
[ bib ]
Each king on an n× n chessboard is said to attack its own square and its neighboring squares, i.e. the nine or fewer squares within one move of the king. A set of kings is said to form an irredundant set if each attacks a square attacked by no other king in the set. We prove that the maximum size of an irredundant set of kings is bounded between (n-1)2/3 and n2/3, and that the minimum size of a maximal irredundant set of kings is bounded between n2/9 and the square of integer part of (n+2)/3, where the latter upper and lower bounds are in fact equal when n is divisible by 3. Results are given for related domination and independence problems.
[21] O. Favaron, M. Mahéo, and J.-F. Saclé. The Randic index and other Graffiti parameters of graphs. MATCH - Commun. Math. Comput. Chem., 47:7-23, 2003.
[ bib ]
Many graph parameters are of interest for both chemists and mathematicians, especially when they are related to the degrees, the distances, or the eigenvalues of the adjacency matrix of the graph. Fajtlowicz developed a program called Graffiti which proposes conjectures obtained by comparing such parameters. We prove or disprove some of these conjectures and give a short survey on general results concerning one of them, the Randic index.
[22] E. J. Cockayne, O. Favaron, W. Goddard, P. J. Grobler, and C. M. Mynhardt. Changing upper irredundance by edge addition. Discrete Math., 266(1-3):185-193, 2003.
[ bib ]
Denote the upper irredundance number of a graph G by IR(G). A graph G is said to be IR-edge-addition-sensitive if its upper irredundance number changes whenever an edge e is added to G. Specifically, G is IR-edge-critical (IR+-edge-critical, respectively) if IR(G+e)<IR(G) (IR(G+e)>IR(G), respectively) for each edge e not in G. We show that if G is IR-edge-addition-sensitive, then G is either IR-edge-critical or IR+-edge-critical. We obtain properties of the latter class of graphs, particularly in the case where β(G)=IR(G)=2 (where β(G) denotes the vertex independence number of G). This leads to an infinite class of 2-IR+-edge-critical graphs.
[23] O. Favaron and M. A. Henning. Upper total domination in claw-free graphs. J. Graph Theory, 44(2):148-158, 2003.
[ bib ]
A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S (other than itself). The maximum cardinality of a minimal total dominating set of G is the upper total domination number of G, denoted by Γt(G). We establish bounds on Γt(G) for claw-free graphs G in terms of the number n of vertices and the minimum degree δ of G. We show that Γt(G) <= 2(n+1)/3 if δ in {1,2}, Γt(G) <= 4n/(δ + 3) if δ in {3,4}, and Γt(G) <= n/2 if δ >= 5. The extremal graphs are characterized.
[24] C. Delorme, O. Favaron, and D. Rautenbach. Closed formulas for the numbers of small independent sets and matchings and an extremal problem for trees. Discrete Appl. Math., 130:503-512, 2003.
[ bib ]
We derive closed formulas for the numbers of independent sets of size at most 4 and matchings of size at most 3 in graphs without small cycles that depend only on the degree sequence and the products of the degrees of adjacent vertices. As a related problem we describe an algorithm that determines a tree of given degree sequence that maximizes the sum of the products of the degrees of adjacent vertices.
[25] O. Favaron. Independence and upper irredundance in claw-free graphs. Discrete Appl. Math., 132(1-3):85-95, 2003.
[ bib ]
It is known that the independence number of a connected claw-free graph G of order n is at most (n+1)/2. We improve this result by showing that this bound still holds for the upper irredundance number IR(G). We characterize the connected claw-free graphs for which IR(G)=(n+1)/2 and give some properties of those graphs for which IR(G)=n/2  if n is even or IR(G)=(n-1)/2 if n is odd.
[26] E. J. Cockayne, O. Favaron, and C. M. Mynhardt. Secure domination, weak roman domination and forbidden subgraphs. Bull. Inst. Combin. Appl., 39:87-100, 2003.
[ bib ]
Bounds are obtained for the secure domination number γs(G) and the weak Roman domination number γr(G) of a simple n-vertex graph G=(V,E). These parameters are the minimum number of guards which must be placed at vertices to protect G with two specific (previously studied) strategies. For all G we show that γs(G)<= ν(G), where ν(G) is the matching number. In claw-free graphs we prove that γr(G)=γs(G)<= 2γ(G), γs(G)<= β(G) if G is also C5-free and (3)/(2)β(G) otherwise, and γs(G)<=3n/(δ(G)+3). For Kt-free graphs with maximum degree Δ we establish the sharp lower bound γs(G)>= n(2Δ-2t+5)/((Δ+1)2-(t-1)(t-2)).
[27] O. Favaron, S. T. Hedetniemi, S. M. Hedetniemi, and D. F. Rall. On k-dependent domination. Discrete Math., 249(1-3):83-94, 2002.
[ bib ]
A subset S of vertices of a graph G is called k-dependent if the maximum degree of the induced subgraph [S] satisfies Δ(S)<= k. A k-dependent dominating set in G is a vertex subset which is both k-dependent and dominating. Similarly, a k-dependent irredundant set in G is a vertex subset which is both k-dependent and irredundant. As usually, the parameters γ k(G) and Γ k(G) (irk(G) and IRk(G) respectively) are defined as the minimum and maximum cardinalities of a minimal k-dependent dominating set (a maximal k-dependent irredundant set resp.). We esblablish some relationships between these parameters and prove that the decision problems corresponding to them are all NP-complete.
[28] O. Favaron, T. W. Haynes, S. T. Hedetniemi, M. A. Henning, and D. J. Knisley. Total irredundance in graphs. Discrete Math., 256(1-2):115-127, 2002.
[ bib ]
A set S of vertices in a graph G is called a total irredundant set if, for each vertex v in G, v or one of its neighbors has no neighbor in S -{v}. We investigate the minimum and maximum cardinalities of maximal total irredundant sets.
[29] C. Delorme, O. Favaron, and D. Rautenbach. On the Randic index. Discrete Math., 257(1):29-38, 2002.
[ bib ]
The Randic index R(G) of a graph G=(V,E) is the sum of (d(u)d(v))-(1)/(2) over all edges uvin E of G. Bollobás and Erdös proved that the Randic index of a graph of order n without isolated vertices is at least sqrt(n-1). They asked for the minimum value of R(G) for graphs G with given minimum degree δ(G). We answer their question for δ(G)=2 and propose a related conjecture. Furthermore, we prove a best-possible lower bound on the Randic index of a triangle-free graph G with given minimum degree δ(G).
[30] G. Bacsó and O. Favaron. Independence, irredundance, degrees and chromatic number in graphs. Discrete Math., 259(1-3):257-262, 2002.
[ bib ]
Let β (G) and IR(G) denote the independence number and the upper irredundance number of a graph G. We prove that in any graph of order n, minimum degree δ and maximum degree Δ<> 0, IR(G)<= n/(1+(δ)/(Δ)) and IR(G)-β (G) <= (Δ -2)/(2Δ)n. The two bounds are attained by arbitrarily large graphs. The second one proves a conjecture by Rautenbach related to the case Δ =3. When the chromatic number χ of G is less than Δ, it can be improved to IR(G)-β (G) <= (χ -2)/(2χ)n in any non-empty graph of order n>= 2.
[31] C. Delorme, O. Favaron, and D. Rautenbach. On the reconstruction of the degree sequence. Discrete Math., 259(1-3):293-300, 2002.
[ bib ]
The edge reconstruction conjecture due to Harary says that all graphs G=(V(G),E(G)) with at least four edges are uniquely determined by their collection of edge-deleted subgraphs, i.e. the graphs of the form G-e for some ein E(G). It is a well-known result that the collection of edge-deleted subgraphs uniquely determines the degree sequence of a graph with at least four edges. In this paper we show that in most cases we need far less than the entire collection of edge-deleted subgraphs in order to reconstruct the degree sequence of a graph. We investigate under which conditions the set of the degree sequences of the edge-deleted subgraphs of some graph G uniquely determines the degree sequence of G.
[32] E. J. Cockayne, O. Favaron, and C. M. Mynhardt. Total domination in claw-free cubic graphs. J. Combin. Math. Combin. Comput., 43:219-225, 2002.
[ bib ]
We prove that the total domination number of an n-vertex claw-free cubic graph is at most n/2.
[33] E. J. Cockayne, O. Favaron, P. J. Grobler, C. M. Mynhardt, and J. Puech. Ramsey properties of generalised irredundant sets in graphs. Discrete Math., 231 (1-3):123-134, 2001.
[ bib ]
For each vertex s of the subset S of vertices of a graph G, we define Boolean variables p,q,r which measure the existence of three kinds of S-private neighbours (S-pns) of s. A 3-variable Boolean function f=f( p,q,r) may be considered as a compound existence property of S-pns. The set S is called an f-set of G if f=1 for all s in S and the class of all f-sets of G is denoted by Ωf. Special cases of Ωf include the independent sets, irredundant sets and CO-irredundant sets of G. For some f in F it is possible to define analogues (involving f-sets) of the classical Ramsey graph numbers. We consider existence theorems for these f-Ramsey numbers and prove that some of them satisfy the well-known recurrence inequality which holds for the classical Ramsey numbers.
[34] O. Favaron, M. A. Henning, J. Puech, and D. Rautenbach. On domination and annihilation in graphs with claw-free blocks. Discrete Math., 231 (1-3):143-151, 2001.
[ bib ]
Let γ(G), ra(G) and ir(G) denote the domination, R-annihilation and irredundance numbers of a graph G, respectively. Graphs whose blocks are claw-free are called CFB-graph. In this paper we establish best possible upper bounds on the ratios γ(G)/ ra(G) and γ(G)/ ir(G) in the class of CFB-graphs. The CFB-graphs generalize several classes of graphs for which such ratios have already been investigated. We introduce a new family of domination parameters simultaneously generalizing the total domination and k-domination numbers. For two integers l>= 0 and k>0 a set X of vertices of a graph G=(V,E) is an l-total k-dominating set of G, if every vertex in X has at least l neighbors in X and every vertex in V-X has at least k neighbors in X. If (at least) one l-total k-dominating set exists, then the l-total k-dominating number γ l,k(G) is the minimum cardinality of such a set. We prove a best possible upper bound on the ratio γ (G)/γ 1,2(G) in the class of CFB-graphs. Our bounds on γ (G)/ ra(G) and γ(G)/ ir(G) for a CFB-graph G will follow as an application of this result.
[35] O. Favaron. Inflated graphs with equal independence number and upper irredundance number. Discrete Math., 236 (1-3):81-94, 2001.
[ bib ]
The inflation GI of a graph G is obtained from G by replacing each vertex x of degree d(x) by a clique X= Kd(x) and each edge xy by an edge between two vertices of the corresponding cliques X and Y of GI in such a way that the edges of GI which come from the edges of G form a matching of GI. We prove that if we denote by β and IR the upper independence and irredundance numbers of a graph, the 2-connected graphs G satisfying β (GI)=IR(GI) are those ones for which maxcut(G) is at most the order of G.
[36] O. Favaron, E. Flandrin, H. Li, and Z. Ryjácek. Clique covering and degree conditions for hamiltonicity in claw-free graphs. Discrete Math., 236 (1-3):65-80, 2001.
[ bib ]
By using the closure concept introduced by the last author, we prove that for any sufficiently large nonhamiltonian claw-free graph G satisfying a degree condition of type σ k(G) > n+k2-4k+7 (where k is a constant), the closure of G can be covered by at most k-1 cliques. Using structural properties of the closure concept, we show a method for characterizing all such nonhamiltonian exceptional graphs with limited clique covering number. The method is explicitly carried out for k<= 6 and illustrated by proving that every 2-connected claw-free graph G of order n>= 77 with δ(G) >= 14 and σ 6(G) > n+19 is either hamiltonian or belongs to a family of easily described exceptions.
[37] E. J. Cockayne, O. Favaron, P. J. Grobler, C. M. Mynhardt, and J. Puech. Generalised Ramsey numbers with respect to classes of graphs. Ars Combin., 59:279-288, 2001.
[ bib ]
Let H1,...,Ht be classes of graphs. The Ramsey number R(H1,...,Ht) is the smallest integer n such that for each t-edge colouring (G1,...,Gt) of Kn, there is at least one i in {1,...,t} such that Gi contains a subgraph Fi in Hi. We take t=2 and determine R(Hl1,Hm1) for all 2<= l<= m and R(Hl2,Hm2) for all 3<= l<= m, where Hji consists of all edge-minimal graphs of order j and minimum degree i.
[38] O. Favaron and P. Fraisse. Hamiltonicity and minimum degree in 3-connected claw-free graphs. J. Combin. Theory Ser. B, 82 (2):297-305, 2001.
[ bib ]
Using Ryjácek's closure, we prove that any 3-connected claw-free graph of order n and minimum degree δ >= (n +38)/(10) is hamiltonian. This improves a theorem of Kuipers and Veldman who got the same result with the stronger hypotheses δ >= (n +29)/(8) and n sufficiently large, and nearly proves their conjecture saying that the result holds as soon as δ >= (n +6)/(10) for n sufficiently large.
[39] O. Favaron and Y. Redouane. Neighborhood unions and regularity in graphs. Theoretical Computer Science, 263:247-254, 2001.
[ bib ]
One way to generalize the concept of degree in a graph is to consider the neighborhood N(S) of an independent set S instead of a simple vertex. The minimum generalized degree of order t of G is then defined, for 1<= t <= α (the independence number of G), by ut= min{|N(S)| : S is independent and |S|=t}. The graph G is said to be ut-regular if |N(S1)|=|N(S2)| for every pair S1,S2 of independent sets of t elements, totally ut-regular (resp. totally ut<= s-regular where s is given <= α) if it is ut-regular for every t<= α (resp. for every t<= s), strongly ut-regular (resp. strongly ut<= s-regular) if |N(S1)|=|N(S2)| for every pair S1,S2 of independent sets of G (resp. every pair of independent sets of order at most s). We determine the strongly ut<= 2-regular graphs and give some properties of the totally ut<= 2-regular and totally ut-regular graphs. Some of our results improve already known results.
[40] E. J. Cockayne, O. Favaron, and C. M. Mynhardt. Irredundance-edge-removal-critical graphs. Utilitas Math., 60:219-228, 2001.
[ bib ]
We characterise the graphs G with ir(G)=3 and ir(G-e)>3.
[41] O. Favaron. Extendability and factor-criticality. Discrete Math., 213 (1-3):115-122, 2000.
[ bib ]
[42] S. Brandt, O. Favaron, and Z. Ryjácek. Closure and stable hamiltonian properties in claw-free graphs. J. Graph Theory, 34 (1):30-41, 2000.
[ bib ]
In the class of k-connected claw-free graphs, we study the stability of some hamiltonian properties under a closure operation introduced by the third author. We prove that

- the properties of pancyclicity, vertex pancyclicity and cycle extendability are not stable for any k (i.e., for any of these properties there is an infinite family of graphs Gk of arbitrarily high connectivity k such that the closure of Gk has the property while the graph Gk does not),

- traceability is a stable property even for k=1,

- homogeneous traceability is not stable for k=2 (although it is stable for k=7). The paper is concluded with several open questions concerning stability of homegeneous traceability and hamiltonian connectedness.

[43] O. Favaron, M. A. Henning, C. M. Mynhardt, and J. Puech. Total domination in graphs with minimum degree three. J. Graph Theory, 34 (1):9-19, 2000.
[ bib ]
[44] O. Favaron, T. W. Haynes, and P. J. Slater. Distance-k independent domination sequences. J. Combin. Math. Combin. Comput., 33:225-237, 2000.
[ bib ]
[45] E. J. Cockayne, O. Favaron, C. M. Mynhardt, and J. Puech. A characterisation of (γ -i)-trees. J. Graph Theory, 34 (4):277-292, 2000.
[ bib ]
[46] O. Favaron. From irredundance to annihilation: a brief overview of some domination parameters of graphs. Saber (Venezuela), 32 (2):64-69, 2000.
[ bib ]
[47] J. Brousek, O. Favaron, and Z. Ryjácek. Forbidden subgraphs, hamiltonicity and closure in claw-free graphs. Discrete Math., 196(1-3):29-50, 1999.
[ bib ]
We study the stability of some classes of graphs defined in terms of forbidden subgraphs under the closure operation introduced by the second author. Using these results, we prove that every 2-connected claw-free and P7-free, or claw-free and Z4-free, or claw-free and eiffel-free graph is either hamiltonian or belongs to a certain class of exceptions (all of them having connectivity 2).
[48] O. Favaron and J. Puech. Irredundant and perfect neighborhood sets in graphs and claw-free graphs. Discrete Math., 197-198 (1-3):269-284, 1999.
[ bib ]
[49] O. Favaron, E. Flandrin, H. Li, and F. Tian. An Ore-type condition for pancyclability. Discrete Math., 206 (1-3):139-144, 1999.
[ bib ]
[50] R. J. Faudree, O. Favaron, E. Flandrin, H. Li, and Z. Liu. On 2-factors in claw-free graphs. Discrete Math., 206 (1-3):131-137, 1999.
[ bib ]
[51] M. Cai, O. Favaron, and H. Li. (2,k)-factor-critical graphs and toughness. Graphs Combin., 15:137-142, 1999.
[ bib ]
[52] C. Delorme and O. Favaron. Graphs with a small max-cut. Util. Math., 56:153-165, 1999.
[ bib ]
[53] O. Favaron, V. Kabanov, and J. Puech. The ratio of three domination parameters in some classes of claw-free graphs. J. Combin. Math. Combin. Comput., 31:151-159, 1999.
[ bib ]
[54] M. Shi, X. Yuan, M. Cai, and O. Favaron. (3,k)-factor-critical graphs and toughness. Graphs Combin., 15:463-471, 1999.
[ bib ]
[55] O. Favaron and J. Puech. Irredundance in grids. Discrete Math., 179:257-265, 1998.
[ bib ]
[56] A. Ainouche, O. Favaron, and H. Li. Global insertion and hamiltonicity in DCT-graphs. Discrete Math., 184:1-13, 1998.
[ bib ]
[57] R. J. Faudree, O. Favaron, and H. Li. Independence, domination, irredundance, and forbidden pairs. J. Combin. Math. Combin. Comput., 26:193-212, 1998.
[ bib ]
[58] O. Favaron. Irredundance in inflated graphs. J. Graph Theory, 28(2):97-104, 1998.
[ bib ]
[59] E. J. Cockayne, O. Favaron, C. M. Mynhardt, and J. Puech. An inequality chain of domination parameters for trees. Discussiones Mathematicae-Graph Theory, 18:127-142, 1998.
[ bib ]
[60] O. Favaron and M. Shi. Minimally k-factor-critical graphs. Austral. J. Combin., 17:89-97, 1998.
[ bib ]
[61] E. J. Cockayne, O. Favaron, C. M. Mynhardt, and J. Puech. Packing, perfect neighbourhood, irredundant and R-annihilated sets in graphs. Austral. J. Combin., 18:253-262, 1998.
[ bib ]
[62] O. Favaron, H. Li, and M. D. Plummer. Some results on Kr-covered graphs. Utilitas Math., 54:33-44, 1998.
[ bib ]
[63] O. Favaron and C. M. Mynhardt. On equality in an upper bound for domination parameters of graphs. J. Graph Theory, 24 (3):221-231, 1997.
[ bib ]
[64] O. Favaron and Y. Redouane. Minimum independent generalized t-degree and independence number in K1,r+1-free graphs. Discrete Math., 165/166:253-261, 1997.
[ bib ]
The minimum independent generalized t-degree of a graph G=(V,E) is ut = min{|N(H)|; H is an independent set of t vertices of G}, with N(H)=Ux in HN(x). In a K1,r+1-free graph, we give an upper bound on ut in terms of r and the independence number α of G. This generalizes already known results on u2 in K1,r+1-free graphs and on ut in K1,3-free graphs.
[65] O. Favaron, F. Tian, and L. Zhang. Independence and hamiltonicity in 3-domination-critical graphs. J. Graph Theory, 25 (3):173-184, 1997.
[ bib ]
[66] O. Favaron, E. Flandrin, and Z. Ryjácek. Factor-criticality and matching extension in DCT-graphs. Discussiones Mathematicae-Graph Theory, 17:271-278, 1997.
[ bib ]
[67] O. Favaron, E. Flandrin, H. Li, Y. Liu, F. Tian, and Z. Wu. Sequences, claws and cyclability of graphs. J. Graph Theory, 21, no 4:357-369, 1996.
[ bib ]
[68] O. Favaron. Least domination in a graph. Discrete Math., 150:115-122, 1996.
[ bib ]
[69] O. Favaron, E. Flandrin, H. Li, and Z. Ryjácek. Shortest walks in almost claw-free graphs. Ars Combin., 42:223-232, 1996.
[ bib ]
[70] O. Favaron. On k - factor-critical graphs. Discussiones Mathematicae-Graph Theory, 16:41-51, 1996.
[ bib ]
[71] O. Favaron. Signed domination in regular graphs. Discrete Math., 158:287-293, 1996.
[ bib ]
[72] O. Favaron, H. Li, and R. H. Schelp. Strong edge colorings of graphs. Discrete Math., 159:103-109, 1996.
[ bib ]
[73] E. J. Cockayne, O. Favaron, and C. M. Mynhardt. Universal maximal packing functions of graphs. Discrete Math., 159:57-68, 1996.
[ bib ]
[74] O. Favaron and C. M. Mynhardt. On the sizes of least common multiples of several pairs of graphs. Ars Combin., 43:181-190, 1996.
[ bib ]
[75] R. J. Faudree, O. Favaron, E. Flandrin, and H. Li. Pancyclism and small cycles in graphs. Discussiones Mathematicae-Graph Theory, 16:27-40, 1996.
[ bib ]
[76] O. Favaron and M. Shi. k-factor-critical graphs and induced subgraphs. Congr. Numer., 122:59-66, 1996.
[ bib ]
[77] D. Amar, O. Favaron, P. Mago, and O. Ordaz. Biclosure and bistability in a balanced bipartite graph. J. Graph Theory, 20, no 4:513-529, 1995.
[ bib ]
[78] O. Favaron and J.-L. Fouquet. On m-centers in Pt-free graphs. Discrete Math., 125:147-152, 1994.
[ bib ]
[79] O. Favaron, D. P. Sumner, and E. Wojcicka. The diameter of domination k-critical graphs. J. Graph Theory, 18, no 7:723-734, 1994.
[ bib ]
[80] O. Favaron, M. Mahéo, and J.-F. Saclé. Some eigenvalue properties in graphs (conjectures of Graffiti - II). Discrete Math., 111:197-220, 1993.
[ bib ]
[81] O. Favaron, P. Mago, C. Maulino, and O. Ordaz. Hamiltonian properties of bipartite graphs and digraphs with bipartite independence 2. SIAM J. Discrete Math., 6, no 2:189-196, 1993.
[ bib ]
[82] R. J. Faudree, O. Favaron, E. Flandrin, and H. Li. The complete closure of a graph. J. Graph Theory, 17, no 4:481-494, 1993.
[ bib ]
[83] O. Favaron, P. Mago, and O. Ordaz. On the bipartite independence number of a balanced bipartite graph. Discrete Math., 121:55-63, 1993.
[ bib ]
[84] O. Favaron. A note on the irredundance number after vertex-deletion. Discrete Math., 121:51-54, 1993.
[ bib ]
[85] C. Delorme, O. Favaron, and M. Mahéo. Isomorphisms of Cayley multigraphs of degree 4 on finite abelian groups. European J. Combin., 13:59-61, 1992.
[ bib ]
[86] O. Favaron. A bound on the independence domination number of a tree. International Journal of Graph Theory, 1, No 1:19-27, 1992.
[ bib ]
[87] E. J. Cockayne, O. Favaron, H. Li, and G. MacGillivray. The product of the independent domination numbers of a graph and its complement. Discrete Math., 90:313-317, 1991.
[ bib ]
[88] O. Favaron, M.-C. Heydemann, J.-C. Meyer, and D. Sotteau. A parameter linked with g-factors and the binding number. Discrete Math., 91:311-316, 1991.
[ bib ]
[89] O. Favaron, M. Mahéo, and J.-F. Saclé. On the residue of a graph. J. Graph Theory, 15:39-64, 1991.
[ bib ]
[90] O. Favaron and D. Kratsch. Ratios of domination parameters. In Advances in Graph Theory, pages 173-182. V. Kulli, Vishwa International Publications, 1991.
[ bib ]
[91] O. Favaron, M. Mahéo, and J.-F. Saclé. Some results on conjectures of Graffiti - I. Ars Combin., 29 C:90-106, 1990.
[ bib ]
[92] J.-C. Bermond, O. Favaron, and M. Mahéo. Hamiltonian decomposition of Cayley graphs of degree 4. J. Combin. Theory Ser. B, 46 (2):142-153, 1989.
[ bib ]
[93] O. Favaron and B. Hartnell. On well-k-covered graphs. J. Combin. Math. Combin. Comput., 6:199-205, 1989.
[ bib ]
[94] O. Favaron, M. Kouider, and M. Mahéo. Edge-vulnerability and mean distance. Networks, 19 (5):493-504, 1989.
[ bib ]
[95] O. Favaron. Two relations between the parameters of independence and irredundance in a graph. Discrete Math., 70:17-20, 1988.
[ bib ]
[96] O. Favaron. A note on the open irredundance in a graph. Congr. Numer., 66:316-318, 1988.
[ bib ]
[97] O. Favaron. k-domination and k-independence in graphs. Ars Combin., 25 C:159-167, 1988.
[ bib ]
[98] O. Favaron and M. Kouider. Path partitions and cycle partitions of eulerian graphs of maximum degree 4. Studia Sci. Math. Hungarica, 23:237-244, 1988.
[ bib ]
[99] O. Favaron. Stabilité, domination, irredondance et autres paramètres de graphes. Thèse d'Etat, Université Paris-Sud, Orsay, France, 1986.
[ bib ]
[100] O. Favaron. Equimatchable factor-critical graphs. J. Graph Theory, 10 (4):439-448, 1986.
[ bib ]
[101] O. Favaron. Stability, domination and irredundance in a graph. J. Graph Theory, 10 (4):429-438, 1986.
[ bib ]
[102] O. Favaron and O. Ordaz. A sufficient condition for oriented graphs to be hamiltonian. Discrete Math., 58:243-252, 1986.
[ bib ]
[103] O. Favaron. On a conjecture of Fink and Jacobson concerning k-domination and k-dependence. J. Combin. Theory Ser. B, 39 (1):101-102, 1985.
[ bib ]
[104] O. Favaron, Z. Lonc, and M. Truszczynski. Decompositions of graphs into graphs with three edges. Ars Combin., 20:125-146, 1985.
[ bib ]
[105] J. Ayel and O. Favaron. Helms are graceful. In Progress in Graph Theory, Proceedings Waterloo 1982, pages 89-92. A. Bondy and U. Murty, Academic Press Canada, 1984.
[ bib ]
[106] O. Favaron. Very well covered graphs. Discrete Math., 42:177-187, 1982.
[ bib ]
[107] E. J. Cockayne, O. Favaron, C. Payan, and A. G. Thomason. Contributions to the theory of domination, independence, and irredundance in graphs. Discrete Math., 33:249-258, 1981.
[ bib ]
[108] O. Favaron, H. Karami, and S.M. Sheikholeslami. Connected domination subdivision numbers of graphs. Utilitas Math., To appear.
[ bib ]
A set S of vertices of a graph G=(V,E) is a connected dominating set if every vertex of V(G) S is adjacent to some vertex in S and the induced subgraph G[S] is connected. The connected domination number γc(G) is the minimum cardinality of a connected dominating set of G. The connected domination subdivision number sdγ_c(G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the connected domination number. In this paper first we establish upper bounds on the connected domination subdivision number in terms of the order n of G or of its edge connectivity number κ'(G). We also prove that γc(G)+sdγ_c(G)<= n-1 with equality if and only if G is a path or a cycle. Finally, we show that the connected domination subdivision number of a graph can be arbitrarily large.
[109] M. Chellali and O. Favaron. On k-star-forming sets in graphs. J. Combin. Math. Combin. Comput., To appear.
[ bib ]
Fink and Jacobson gave a generalization of the concepts of domination and independence in graphs which extends only partially the well-known inequality chain γ(G)<=i(G)<=β(G)<=Γ(G) between the usual parameters of domination and independence. If a k-independent set is defined as a subset of vertices inducing in G a subgraph of maximum degree less than k, we introduce the property which makes a k-independent set maximal. This leads us to the notion of k-star-forming set. The corresponding parameters sfk(G) and SFk(G) satisfy sfk(G)<=ik(G)<=βk(G)<=SFk(G) where ik(G) and βk(G) are respectively the minimum and the maximum cardinality of a maximal k-independent set. We initiate the study of sfk(G) and SFk(G) and give some results in particular classes of graphs as trees, chordal graphs and K1,r-free graphs.
[110] O. Favaron, H. Karami, and S.M. Sheikholeslami. Paired-domination number of a graph and its complement. Discrete Math., to appear.
[ bib ]
[111] H. Aram, S.M. Sheikholeslami, and O. Favaron. Trees with domination subdivision number three. Discrete Math., to appear.
[ bib ]
A set S of vertices of a graph G=(V,E) is a dominating set if every vertex of V(G) S is adjacent to some vertex in S. The domination number γ(G) is the minimum cardinality of a dominating set of G. The domination subdivision number sdγ(G) is the minimum number of edges that must be subdivided in order to increase the domination number. Velammal showed that for any tree T of order at least 3, 1<= sdγ(T)<= 3. In this paper, we give two characterizations of trees whose domination subdivision number is 3 and a polynomial algorithm to recognize them.
[112] M. Chellali, O. Favaron, A. Hansberg, and L. Volkmann. On the p-domination, the total domination and the connected domination numbers of graphs. J. Combin. Math. Combin. Comput., to appear.
[ bib ]
Fink and Jacobson [?] showed in 1985 that if G is a graph with Δ(G) >= p >= 2, then γp(G) >= γ(G) + p - 2. In this paper we will give some sufficient conditions for a graph G such that γp(G) >= γ(G) + p - 1. We will show that for block graphs G the inequality γp(G) >= γt(G) + p - 2 is valid and that for trees T the inequality γp(T) >= γc(T)+p-1 holds. Further, we characterize the trees T with γp(T) = γc(T) + p - 1, γp(T) = γt(T) + p - 2, γp(T) = γt(T) + p - 1 and γp(T) = γ(T) + p - 1.
[113] E. J. Cockayne, O. Favaron, A. Finbow, and C. M. Mynhardt. Open irredundance and maximum degree in graphs. Discrete Math., to appear.
[ bib ]
A necessary and sufficient condition for an open irredundant set of vertices of a graph to be maximal is obtained. This result is used to show that the minimum cardinality amongst the open irredundant sets in an n-vertex isolate-free graph with maximum degree Δ is at least n(3Δ -1)/(2Δ 3-5Δ 2+8Δ -1) for Δ >= 5, n/8 for Δ =4 and 2n/11 for Δ =3. The bounds are best possible.
[114] M. Blidia, O. Favaron, and R. Lounes. Locating-domination, 2-domination and independence in trees. Australasian J. Combin., to appear.
[ bib ]
[115] O. Favaron, H. Karami, and S.M. Sheikholeslami. Disproof of a conjecture on the subdivision domination number of a graph. Graphs and Combinatorics, to appear.
[ bib ]
A set S of vertices of a graph G=(V,E) is a dominating set if every vertex of V(G) S is adjacent to some vertex in S. The domination number γ(G) is the minimum cardinality of a dominating set of G. The domination subdivision number sdγ(G) is the minimum number of edges that must be subdivided once in order to increase the domination number. Haynes et al. (Discussiones Mathematicae Graph Theory 21 (2001) 239-253) conjectured that sdγ(G)<= δ(G)+1 for any graph G with δ(G)>= 2. In this note we first give a counterexample to this conjecture in general and then we prove it for a particular class of graphs.

This file has been generated by bibtex2html 1.75