The induced path function, monotonicity and betweenness

The geodesic interval function I of a connected graph allows an axiomatic characterization involving axioms on the function only, without any reference to distance, as was shown by Nebeský [20]. Surprisingly, Nebeský [23] showed that, if no further restrictions are imposed, the induced path function J of a connected graph G does not allow such an axiomatic characterization. Here J(u,v) consists of the set of vertices lying on the induced paths between u and v. This function is a special instance of a transit function. In this paper we address the question what kind of restrictions could be imposed to obtain axiomatic characterizations of J. The function J satisfies betweenness if w∈J(u,v), with w≠u, implies u∉J(w,v) and x∈J(u,v) implies J(u,x)⊆J(u,v). It is monotone if x,y∈J(u,v) implies J(x,y)⊆J(u,v). In the case where we restrict ourselves to functions J that satisfy betweenness, or monotonicity, we are able to provide such axiomatic characterizations of J by transit axioms only. The graphs involved can all be characterized by forbidden subgraphs.     

A sufficient condition for pancyclability of graphs

Let G be a graph of order n and S be a vertex set of q vertices. We call G,S-pancyclable, if for every integer i with 3≤i≤q there exists a cycle C in G such that |V(C)∩S|=i. For any two nonadjacent vertices u,v of S, we say that u,v are of distance two in S, denoted by d_S(u,v)=2, if there is a path P in G connecting u and v such that |V(P)∩S|≤3. In this paper, we will prove that if G is 2-connected and for all pairs of vertices u,v of S with d_S(u,v)=2, , then there is a cycle in G containing all the vertices of S. Furthermore, if for all pairs of vertices u,v of S with d_S(u,v)=2, , then G is S-pancyclable unless the subgraph induced by S is in a class of special graphs. This generalizes a result of Fan [G. Fan, New sufficient conditions for cycles in graphs, J. Combin. Theory B 37 (1984) 221-227] for the case when S=V(G).     

3-Factor-criticality in domination critical graphs

A graph G is said to be k-γ-critical if the size of any minimum dominating set of vertices is k, but if any edge is added to G the resulting graph can be dominated with k-1 vertices. The structure of k-γ-critical graphs remains far from completely understood when k?3.A graph G is factor-critical if G-v has a perfect matching for every vertex v∈V(G) and is bicritical if G-u-v has a perfect matching for every pair of distinct vertices u,v∈V(G). More generally, a graph is said to be k-factor-critical if G-S has a perfect matching for every set S of k vertices in G. In three previous papers [N. Ananchuen, M.D. Plummer, Some results related to the toughness of 3-domination-critical graphs, Discrete Math. 272 (2003) 5-15; N. Ananchuen, M.D. Plummer, Matching properties in domination critical graphs, Discrete Math. 277 (2004) 1-13; N. Ananchuen, M.D. Plummer, Some results related to the toughness of 3-domination-critical graphs. II. Utilitas Math. 70 (2006) 11-32], we explored the toughness of 3-γ-critical graphs and some of their matching properties. In particular, we obtained some properties which are sufficient for a 3-γ-critical graph to be factor-critical and, respectively, bicritical. In the present work, we obtain similar results for k-factor-critical graphs when k=3.     

Variations of Y-dominating functions on graphs

Let Y be a subset of real numbers. A Y-dominating function of a graph G=(V,E) is a function f:V→Y such that for all vertices v∈V, where N_G[v]={v}∪{u|(u,v)∈E}. Let for any subset S of V and let f(V) be the weight of f. The Y-domination problem is to find a Y-dominating function of minimum weight for a graph G=(V,E). In this paper, we study the variations of Y-domination such as {k}-domination, k-tuple domination, signed domination, and minus domination for some classes of graphs. We give formulas to compute the {k}-domination, k-tuple domination, signed domination, and minus domination numbers of paths, cycles, n-fans, n-wheels, n-pans, and n-suns. Besides, we present a unified approach to these four problems on strongly chordal graphs. Notice that trees, block graphs, interval graphs, and directed path graphs are subclasses of strongly chordal graphs. This paper also gives complexity results for the problems on doubly chordal graphs, dually chordal graphs, bipartite planar graphs, chordal bipartite graphs, and planar graphs.     

A survey of stratified domination in graphs

A graph G is 2-stratified if its vertex set is partitioned into two nonempty classes (each of which is a stratum or a color class). We color the vertices in one color class red and the other color class blue. Let F be a 2-stratified graph with one fixed blue vertex v specified. We say that F is rooted at v. The F-domination number of a graph G is the minimum number of red vertices of G in a red-blue coloring of the vertices of G such that for every blue vertex v of G, there is a copy of F in G rooted at v. In this paper, we survey recent results on the F-domination number for various 2-stratified graphs F.     

On the complexity of the independent set problem in triangle graphs

We consider the complexity of the maximum (maximum weight) independent set problem within triangle graphs, i.e., graphs G satisfying the following triangle condition: for every maximal independent set I in G and every edge uv in G−I, there is a vertex w∈I such that {u,v,w} is a triangle in G. We also introduce a new graph parameter (the upper independent neighborhood number) and the corresponding upper independent neighborhood set problem. We show that for triangle graphs the new parameter is equal to the independence number. We prove that the problems under consideration are NP-complete, even for some restricted subclasses of triangle graphs, and provide several polynomially solvable cases for these problems within triangle graphs. Furthermore, we show that, for general triangle graphs, the maximum independent set problem and the upper independent neighborhood set problem cannot be polynomially approximated within any fixed constant factor greater than one unless P=NP.     

Kernels and some operations in edge-coloured digraphs

Let D be an edge-coloured digraph, V(D) will denote the set of vertices of D; a set N⊆V(D) is said to be a kernel by monochromatic paths of D if it satisfies the following two conditions: For every pair of different vertices u,v∈N there is no monochromatic directed path between them and; for every vertex x∈V(D)−N there is a vertex y∈N such that there is an xy-monochromatic directed path.In this paper we consider some operations on edge-coloured digraphs, and some sufficient conditions for the existence or uniqueness of kernels by monochromatic paths of edge-coloured digraphs formed by these operations from another edge-coloured digraphs.     

Labeling graphs with two distance constraints

Given a graph G and integers p,q,d₁ and d₂, with p>q, d₂>d₁?1, an L(d₁,d₂;p,q)-labeling of G is a function f:V(G)→{0,1,2,…,n} such that |f(u)−f(v)|?p if d_G(u,v)?d₁ and |f(u)−f(v)|?q if d_G(u,v)?d₂. A k-L(d₁,d₂;p,q)-labeling is an L(d₁,d₂;p,q)-labeling f such that max_v∈V(G)f(v)?k. The L(d₁,d₂;p,q)-labeling number ofG, denoted by , is the smallest number k such that G has a k-L(d₁,d₂;p,q)-labeling. In this paper, we give upper bounds and lower bounds of the L(d₁,d₂;p,q)-labeling number for general graphs and some special graphs. We also discuss the L(d₁,d₂;p,q)-labeling number of G, when G is a path, a power of a path, or Cartesian product of two paths.     

Labeling trees with a condition at distance two

An L(h,k)-labeling of a graph G is an integer labeling of vertices of G, such that adjacent vertices have labels which differ by at least h, and vertices at distance two have labels which differ by at least k. The span of an L(h,k)-labeling is the difference between the largest and the smallest label. We investigate L(h,k)-labelings of trees of maximum degree Δ, seeking those with small span. Given Δ, h and k, span λ is optimal for the class of trees of maximum degree Δ, if λ is the smallest integer such that every tree of maximum degree Δ has an L(h,k)-labeling with span at most λ. For all parameters Δ,h,k, such that h<k, we construct L(h,k)-labelings with optimal span. We also establish optimal span of L(h,k)-labelings for stars of arbitrary degree and all values of h and k.     

Degree conditions for group connectivity

Let G be a 2-edge-connected simple graph on n≥13 vertices and A an (additive) abelian group with |A|≥4. In this paper, we prove that if for every uv∉E(G), max{d(u),d(v)}≥n/4, then either G is A-connected or G can be reduced to one of K_2,3,C₄ and C₅ by repeatedly contracting proper A-connected subgraphs, where C_k is a cycle of length k. We also show that the bound n≥13 is the best possible.     

More on “Connected (n, m)-graphs with minimum and maximum zeroth-order general Randi? index”

Let G be a graph and d(u) denote the degree of a vertex u in G. The zeroth-order general Randi? index ⁰R_α(G) of the graph G is defined as ∑_u∈V(G)d(u)^α, where the summation goes over all vertices of G and α is an arbitrary real number. In this paper we correct the proof of the main Theorem 3.5 of the paper by Hu et al. [Y. Hu, X. Li, Y. Shi, T. Xu, Connected (n,m)-graphs with minimum and maximum zeroth-order general Randi? index, Discrete Appl. Math. 155 (8) (2007) 1044-1054] and give a more general Theorem. We finally characterize ¹ for α<0 the connected G(n,m)-graphs with maximum value ⁰R_α(G(n,m)), where G(n,m) is a simple connected graph with n vertices and m edges.     

Minimum monopoly in regular and tree graphs

In this paper we consider a graph optimization problem called minimum monopoly problem, in which it is required to find a minimum cardinality set S⊆V, such that, for each u∈V, |N[u]∩S|?|N[u]|/2 in a given graph G=(V,E). We show that this optimization problem does not have a polynomial-time approximation scheme for k-regular graphs (k?5), unless P=NP. We show this by establishing two L-reductions (an approximation preserving reduction) from minimum dominating set problem for k-regular graphs to minimum monopoly problem for 2k-regular graphs and to minimum monopoly problem for (2k-1)-regular graphs, where k?3. We also show that, for tree graphs, a minimum monopoly set can be computed in linear time.     

Minimal rankings and the arank number of a path

Given a graph G, a function f:V(G)→{1,2,…,k} is a k-ranking of G if f(u)=f(v) implies every u-v path contains a vertex w such that f(w)>f(u). A k-ranking is minimal if the reduction of any label greater than 1 violates the described ranking property. The arank number of a graph, denoted ψ_r(G), is the largest k such that G has a minimal k-ranking. We present new results involving minimal k-rankings of paths. In particular, we determine ψ_r(P_n), a problem posed by Laskar and Pillone in 2000.     

Linear-time certifying algorithms for near-graphical sequences

A sequence 〈d₁,d₂,…,d_n〉 of non-negative integers is graphical if it is the degree sequence of some graph, that is, there exists a graph G on n vertices whose ith vertex has degree d_i, for 1≤i≤n. The notion of a graphical sequence has a natural reformulation and generalization in terms of factors of complete graphs.If H=(V,E) is a graph and g and f are integer-valued functions on the vertex set V, then a (g,f)-factor of H is a subgraph G=(V,F) of H whose degree at each vertex v∈V lies in the interval [g(v),f(v)]. Thus, a (0,1)-factor is just a matching of H and a (1, 1)-factor is a perfect matching of H. If H is complete then a (g,f)-factor realizes a degree sequence that is consistent with the sequence of intervals 〈[g(v₁),f(v₁)],[g(v₂),f(v₂)],…,[g(v_n),f(v_n)]〉.Graphical sequences have been extensively studied and admit several elegant characterizations. We are interested in extending these characterizations to non-graphical sequences by introducing a natural measure of “near-graphical”. We do this in the context of minimally deficient (g,f)-factors of complete graphs. Our main result is a simple linear-time greedy algorithm for constructing minimally deficient (g,f)-factors in complete graphs that generalizes the method of Hakimi and Havel (for constructing (f,f)-factors in complete graphs, when possible). It has the added advantage of producing a certificate of minimum deficiency (through a generalization of the Erdös-Gallai characterization of (f,f)-factors in complete graphs) at no additional cost.     

Triangular line graphs and word sense disambiguation

Linguists often represent the relationships between words in a collection of text as an undirected graph G=(V,E), where V is the vocabulary and vertices are adjacent in G if and only if the words that they represent co-occur in a relevant pattern in the text. Ideally, the words with similar meanings give rise to the vertices of a component of the graph. However, many words have several distinct meanings, preventing components from characterizing distinct semantic fields. This paper examines how the structural properties of triangular line graphs motivate the use of a clustering coefficient on the triangular line graph, thereby helping to identify polysemous words. The triangular line graph of G, denoted by T(G), is the subgraph of the line graph of G where two vertices are adjacent if the corresponding edges in G belong to a K₃.     

Spanning trails containing given edges

A graph G is Eulerian-connected if for any u and v in V(G), G has a spanning (u,v)-trail. A graph G is edge-Eulerian-connected if for any e^′ and e^″ in E(G), G has a spanning (e^′,e^″)-trail. For an integer r?0, a graph is called r-Eulerian-connected if for any X⊆E(G) with |X|?r, and for any , G has a spanning (u,v)-trail T such that X⊆E(T). The r-edge-Eulerian-connectivity of a graph can be defined similarly. Let θ(r) be the minimum value of k such that every k-edge-connected graph is r-Eulerian-connected. Catlin proved that θ(0)=4. We shall show that θ(r)=4 for 0?r?2, and θ(r)=r+1 for r?3. Results on r-edge-Eulerian connectivity are also discussed.     

On (d,1)-total numbers of graphs

A (d,1)-total labelling of a graph G assigns integers to the vertices and edges of G such that adjacent vertices receive distinct labels, adjacent edges receive distinct labels, and a vertex and its incident edges receive labels that differ in absolute value by at least d. The span of a (d,1)-total labelling is the maximum difference between two labels. The (d,1)-total number, denoted , is defined to be the least span among all (d,1)-total labellings of G. We prove new upper bounds for , compute some for complete bipartite graphs K_m,n, and completely determine all for d=1,2,3. We also propose a conjecture on an upper bound for in terms of the chromatic number and the chromatic index of G.     

Finding monotone paths in edge-ordered graphs

An edge-ordering of a graph G=(V,E) is a one-to-one function f from E to a subset of the set of positive integers. A path P in G is called an f-ascent if f increases along the edge sequence of P. The heighth(f) of f is the maximum length of an f-ascent in G.In this paper we deal with computational problems concerning finding ascents in graphs. We prove that for a given edge-ordering f of a graph G the problem of determining the value of h(f) is NP-hard. In particular, the problem of deciding whether there is an f-ascent containing all the vertices of G is NP-complete. We also study several variants of this problem, discuss randomized and deterministic approaches and provide an algorithm for the finding of ascents of order at least k in graphs of order n in running time O(4^kn^O(1)).     

An extremal problem on non-full colorable graphs

For a given graph G of order n, a k-L(2,1)-labelling is defined as a function f:V(G)→{0,1,2,…k} such that |f(u)-f(v)|?2 when d_G(u,v)=1 and |f(u)-f(v)|?1 when d_G(u,v)=2. The L(2,1)-labelling number of G, denoted by λ(G), is the smallest number k such that G has a k-L(2,1)-labelling. The hole index ρ(G) of G is the minimum number of integers not used in a λ(G)-L(2,1)-labelling of G. We say G is full-colorable if ρ(G)=0; otherwise, it will be called non-full colorable. In this paper, we consider the graphs with λ(G)=2m and ρ(G)=m, where m is a positive integer. Our main work generalized a result by Fishburn and Roberts [No-hole L(2,1)-colorings, Discrete Appl. Math. 130 (2003) 513-519].