On the characterization of trees with signed edge domination numbers 1, 2, 3, or 4

Let G=(V,E) be a simple graph. For an edge e of G, the closed edge-neighbourhood of e is the set N[e]={e^′∈E|e^′ is adjacent to e}∪{e}. A function f:E→{1,−1} is called a signed edge domination function (SEDF) of G if ∑_e^′∈N[e]f(e^′)≥1 for every edge e of G. The signed edge domination number of G is defined as . In this paper, we characterize all trees T with signed edge domination numbers 1, 2, 3, or 4.     

On Fixed Edges and Edge-Reconstruction of Series-Parallel Networks

 An edge e of a graph G is said to be a fixed edge if G−e+e ^′≅G implies that e ^′=e, and a forced edge if G−e+e ^′ is an edge-reconstruction of G implies that e ^′=e. In this paper, we use the method of excludable configurations to investigate the fixed edges and the forced edges of series-parallel networks. It is proved that all series-parallel networks contain fixed edges except P ₃∨K ₁ and P ₄∨K ₁, and that all series-parallel networks are edge-reconstructible. Received: December 22, 1997 Final version received: July 21, 1999     

Depth of Initial Ideals of Normal Edge Rings

Let G be a finite graph on the vertex set [d] = {1,…, d} with the edges e ₁,…, e _n and K[t] = K[t ₁,…, t _d ] the polynomial ring in d variables over a field K. The edge ring of G is the semigroup ring K[G] which is generated by those monomials t ^e  = t _i t _j such that e = {i, j} is an edge of G. Let K[x] = K[x ₁,…, x _n ] be the polynomial ring in n variables over K, and define the surjective homomorphism π: K[x] → K[G] by setting π(x _i ) = t ^{e _i} for i = 1,…, n. The toric ideal I _G of G is the kernel of π. It will be proved that, given integers f and d with 6 ≤ f ≤ d, there exists a finite connected nonbipartite graph G on [d] together with a reverse lexicographic order <_rev on K[x] and a lexicographic order <_lex on K[x] such that (i) K[G] is normal with Krull-dim K[G] = d, (ii) depth K[x]/in_<rev (I _G ) = f and K[x]/in_<lex (I _G ) is Cohen–Macaulay, where in_<rev (I _G ) (resp., in_<lex (I _G )) is the initial ideal of I _G with respect to <_rev (resp., <_lex) and where depth K[x]/in_<rev (I _G ) is the depth of K[x]/in_<rev (I _G ).     

Edge-Distinguishing Index of a Graph

We introduce a concept of edge-distinguishing colourings of graphs. A closed neighbourhood of an edge \({e\in E(G)}\) is a subgraph N[e] induced by e and all edges adjacent to it. We say that a colouring c : E(G) → C does not distinguish two edges e ₁ and e ₂ if there exists an isomorphism φ of N[e ₁] onto N[e ₂] such that φ(e ₁) = e ₂ and φ preserves colours of c. An edge-distinguishing index of a graph G is the minimum number of colours in a proper colouring which distinguishes every two distinct edges of G. We determine the edge-distinguishing index for cycles, paths and complete graphs.     

List total colorings of series-parallel graphs

A total coloring of a graph G is a coloring of all elements of G, i.e., vertices and edges, in such a way that no two adjacent or incident elements receive the same color. Let L(x) be a set of colors assigned to each element x of G. Then a list total coloring of G is a total coloring such that each element x receives a color contained in L(x). The list total coloring problem asks whether G has a list total coloring. In this paper, we first show that the list total coloring problem is NP-complete even for series-parallel graphs. We then give a sufficient condition for a series-parallel graph to have a list total coloring, that is, we prove a theorem that any series-parallel graph G has a list total coloring if |L(v)|min{5,Δ+1} for each vertex v and |L(e)|max{5,d(v)+1,d(w)+1} for each edge e=vw, where Δ is the maximum degree of G and d(v) and d(w) are the degrees of the ends v and w of e, respectively. The theorem implies that any series-parallel graph G has a total coloring with Δ+1 colors if Δ4. We finally present a linear-time algorithm to find a list total coloring of a given series-parallel graph G if G satisfies the sufficient condition.     

Cycles in Partially Square Graphs

. In this work we consider finite undirected simple graphs. If G=(V,E) is a graph we denote by α(G) the stability number of G. For any vertex x let N[x] be the union of x and the neighborhood N(x). For each pair of vertices ab of G we associate the set J(a,b) as follows. J(a,b)={u∈N[a]∩N[b]∣N(u)⊆N[a]∪N[b]}. Given a graph G, its partially squareG ^* is the graph obtained by adding an edge uv for each pair u,v of vertices of G at distance 2 whenever J(u,v) is not empty. In the case G is a claw-free graph, G ^* is equal to G ². If G is k-connected, we cover the vertices of G by at most ⌈α(G ^*)/k⌉ cycles, where α(G ^*) is the stability number of the partially square graph of G. On the other hand we consider in G ^* conditions on the sum of the degrees. Let G be any 2-connected graph and t be any integer (t≥2). If ∑ _{x ∈ S} deg _G (x)≥|G|, for every t-stable set S⊆V(G) of G ^* then the vertex set of G can be covered with t−1 cycles. Different corollaries on covering by paths are given. Received: January 22, 1997 Final version received: February 15, 2000     

Hamiltonism and Partially Square Graphs

 Given a graph G, we define its partially square graph G ^* as the graph obtained by adding edges uv whenever the vertices u and v have a common neighbor x satisfying the condition N _G[x]⊆N _G[u]∪N _G [v], where N _G[x]=N _G(x)∪{x}. In particular, this condition is satisfied if x does not center a claw (an induced K _1,3). Obviously G⊆G ^*⊆G ², where G ² is the square of G. We prove that a k-connected graph (k≥2) G is hamiltonian if the independence number α(G ^*) of G ^* does not exceed k. If we replace G ^* by G we get a well known result of Chvátal and Erdo?s. If G is claw-free and G ^* is replaced by G ² then we obtain a result of Ainouche, Broersma and Veldman. Relationships between connectivity of G and independence number of G ^* for other hamiltonian properties are also given in this paper. Received: June 17, 1996 Revised: October 30, 1998     

Distance-Dominating Cycles in Quasi Claw-Free Graphs

We say that a graph G is quasi claw-free if every pair (a ₁, a ₂) of vertices at distance 2 satisfies {u∈N (a ₁)∩N (a ₂) | N[u]⊆N[a ₁]∪N [a ₂]}≠∅. A cycle C is m-dominating if every vertex of G is of distance at most m from C. We prove that if G is a κ-connected (κ≥2) quasi claw-free graph then either G has an m-dominating cycle or G has a set of at least κ+1 vertices such that the distance between every pair of them is at least 2m+3. Received: June 12, 1996 Revised: November 9, 1998     

Weakly connected domination stable trees

A dominating set D ⊆ V(G) is a weakly connected dominating set in G if the subgraph G[D] _w = (N _G [D], E _w ) weakly induced by D is connected, where E _w is the set of all edges having at least one vertex in D. Weakly connected domination number _γw (_G) of a graph G is the minimum cardinality among all weakly connected dominating sets in G. A graph G is said to be weakly connected domination stable or just _γw -stable if _γw (G) = _{γ w} (G + e) for every edge e belonging to the complement Ḡ of G. We provide a constructive characterization of weakly connected domination stable trees.      

The Linear Arboricity of Series-Parallel Graphs

 The linear arboricity la(G) of a graph G is the minimum number of linear forests which partition the edges of G. A graph is called series-parallel if it contains no subgraphs homeomorphic to K ₄. In this paper, we prove that for any series-parallel graph G having Δ (G)≥3. Since an outerplanar graph is a series-parallel graph, this is also true for any outerplanar graph. Received: August 20, 1997 Revised: March 12, 1999     

Fractional and integral colourings

LetG=(V, E) be an undirected graph andc any vector in ℤ ^V(G) ₊. Denote byχ(G _c) (resp.η(G _c)) the chromatic number (resp. fractional chromatic number) ofG with respect toc. We study graphs for whichχ(G _c)−[η(G _c)]⩽1. We show that for the class of graphs satisfyingχ(G _c)=[η(G _c)] (a class generalizing perfect graphs), an analogue of the Duplication Lemma does not hold. We also describe a 2-vertex cut decomposition procedure related to the integer decomposition property. We use this procedure to show thatχ(G _c)=[η(G _c)] for series-parallel graphs andχ(G _c)⩽[η(G _c)]+1 for graphs that do not have the 4-wheel as a minor. The work of this author was supported by the Natural Sciences and Engineering Research Council of Canada (NSERCC) under grant A9126.     

On the algebraic independence in the selberg class

We prove that a functionF of the Selberg class ℐ is ab-th power in ℐ, i.e.,F=H ^b for someHσ ℐ, if and only ifb divides the order of every zero ofF and of everyp-componentF _p. This implies that the equationF ^a=G^b with (a, b)=1 has the unique solutionF=H ^b andG=H ^a in ℐ. As a consequence, we prove that ifF andG are distinct primitive elements of ℐ, then the transcendence degree of ℂ[F,G] over ℂ is two.     

Some Notes on Signed Edge Domination in Graphs

The closed neighborhood N_G[e] of an edge e in a graph G is the set consisting of e and of all edges having an end-vertex in common with e. Let f be a function on E(G), the edge set of G, into the set {−1, 1}. If for each e ∈ E(G), then f is called a signed edge dominating function of G. The signed edge domination number γ_s^′(G) of G is defined as . Recently, Xu proved that γ_s^′(G) ≥ |V(G)| − |E(G)| for all graphs G without isolated vertices. In this paper we first characterize all simple connected graphs G for which γ_s^′(G) = |V(G)| − |E(G)|. This answers Problem 4.2 of [4]. Then we classify all simple connected graphs G with precisely k cycles and γ_s^′(G) = 1 − k, 2 − k. A. Khodkar: Research supported by a Faculty Research Grant, University of West Georgia. Send offprint requests to: Abdollah Khodkar.     

New edge neighborhood graphs

Let G be an undirected simple connected graph, and e = uv be an edge of G. Let N _G(e) be the subgraph of G induced by the set of all vertices of G which are not incident to e but are adjacent to u or v. Let N _e be the class of all graphs H such that, for some graph G,N _G (e) H for every edge e of G. Zelinka [3] studied edge neighborhood graphs and obtained some special graphs in N _e. Balasubramanian and Alsardary [1] obtained some other graphs in N _e. In this paper we given some new graphs in N _e.     

Circular perfect graphs

For 1 ≤ d ≤ k, let K_k/d be the graph with vertices 0, 1, …, k ? 1, in which i ～j if d ≤ |i ? j| ≤ k ? d. The circular chromatic number χ_c(G) of a graph G is the minimum of those k/d for which G admits a homomorphism to K_k/d. The circular clique number ω_c(G) of G is the maximum of those k/d for which K_k/d admits a homomorphism to G. A graph G is circular perfect if for every induced subgraph H of G, we have χ_c(H) = ω_c(H). In this paper, we prove that if G is circular perfect then for every vertex x of G, N_G[x] is a perfect graph. Conversely, we prove that if for every vertex x of G, N_G[x] is a perfect graph and G ? N[x] is a bipartite graph with no induced P₅ (the path with five vertices), then G is a circular perfect graph. In a companion paper, we apply the main result of this paper to prove an analog of Haj?os theorem for circular chromatic number for k/d ≥ 3. Namely, we shall design a few graph operations and prove that for any k/d ≥ 3, starting from the graph K_k/d, one can construct all graphs of circular chromatic number at least k/d by repeatedly applying these graph operations. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 186–209, 2005     

Partitioning a graph into convex sets

Let G be a finite simple graph. Let S⊆V(G), its closed interval I[S] is the set of all vertices lying on shortest paths between any pair of vertices of S. The set S is convex if I[S]=S. In this work we define the concept of a convex partition of graphs. If there exists a partition of V(G) into p convex sets we say that G is p-convex. We prove that it is NP-complete to decide whether a graph G is p-convex for a fixed integer p≥2. We show that every connected chordal graph is p-convex, for 1≤p≤n. We also establish conditions on n and k to decide if the k-th power of a cycle C_n is p-convex. Finally, we develop a linear-time algorithm to decide if a cograph is p-convex.     

Near-proper vertex 2-colorings of sparse graphs

A graph G is (2, 1)-colorable if its vertices can be partitioned into subsets V ₁ and V ₂ such that each component in G[V ₁] contains at most two vertices while G[V ₂] is edgeless. We prove that every graph with maximum average degree mad(G) < 7/3 is (2, 1)-colorable. It follows that every planar graph with girth at least 14 is (2, 1)-colorable. We also construct a planar graph G _n with mad (G _n ) = (18n − 2)/(7n − 1) that is not (2, 1)-colorable.     

Bipartite Graphs Whose Edge Algebras Are Complete Intersections

Let R be a monomial subalgebra of k[x₁,…,x_N] generated by square free monomials of degree two. This paper addresses the following question: when is R a complete intersection? For such a k-algebra we can associate a graph G whose vertices are x₁,…,x_N and whose edges are {(x_i, x_j)|x_ix_j  R}. Conversely, for any graph G with vertices {x₁,…,x_N} we define the edge algebra associated with G as the subalgebra of k[x₁,…,x_N] generated by the monomials {x_ix_j|(x_i, x_j) is an edge of G}. We denote this monomial algebra by k[G]. This paper describes all bipartite graphs whose edge algebras are complete intersections.     

Removable edges in cycles of a <Emphasis Type="Italic">k</Emphasis>-connected graph

An edge e of a k-connected graph G is said to be a removable edge if G ⊖ e is still k-connected, where G ⊖ e denotes the graph obtained from G by deleting e to get G − e, and for any end vertex of e with degree k − 1 in G − e, say x, delete x, and then add edges between any pair of non-adjacent vertices in N _G−e (x). The existence of removable edges of k-connected graphs and some properties of 3-connected graphs and 4-connected graphs have been investigated. In the present paper, we investigate some properties of k-connected graphs and study the distribution of removable edges on a cycle in a k-connected graph (k ≥ 4).     

Bounds on global secure sets in cactus trees

Let G = (V, E) be a graph. A global secure set SD ⊆ V is a dominating set which satisfies the condition: for all X ⊆ SD, |N[X] ∩ SD| ≥ | N[X] − SD|. A global defensive alliance is a set of vertices A that is dominating and satisfies a weakened condition: for all x ∈ A, |N[x] ∩ A| ≥ |N[x] − A|. We give an upper bound on the cardinality of minimum global secure sets in cactus trees. We also present some results for trees, and we relate them to the known bounds on the minimum cardinality of global defensive alliances.