New edge neighborhood graphs

Ali A. Ali; Salar Y. Alsardary

Displaying similar documents to “New edge neighborhood graphs”

On integral sum graphs with a saturated vertex

Zhibo Chen (2010)

Czechoslovak Mathematical Journal

Similarity:

As introduced by F. Harary in 1994, a graph $G$ is said to be an $i n t e g r a l$ $s u m$ $g r a p h$ if its vertices can be given a labeling $f$ with distinct integers so that for any two distinct vertices $u$ and $v$ of $G$ , $u v$ is an edge of $G$ if and only if $f (u) + f (v) = f (w)$ for some vertex $w$ in $G$ . We prove that every integral sum graph with a saturated vertex, except the complete graph $K_{3}$ , has edge-chromatic number equal to its maximum degree. (A vertex of a graph $G$ is said to be if it is adjacent to every...

Rotation and jump distances between graphs

Gary Chartrand, Heather Gavlas, Héctor Hevia, Mark A. Johnson (1997)

Discussiones Mathematicae Graph Theory

Similarity:

A graph H is obtained from a graph G by an edge rotation if G contains three distinct vertices u,v, and w such that uv ∈ E(G), uw ∉ E(G), and H = G-uv+uw. A graph H is obtained from a graph G by an edge jump if G contains four distinct vertices u,v,w, and x such that uv ∈ E(G), wx∉ E(G), and H = G-uv+wx. If a graph H is obtained from a graph G by a sequence of edge jumps, then G is said to be j-transformed into H. It is shown that for every two graphs G and H of the same order (at least...

Graceful signed graphs

Mukti Acharya, Tarkeshwar Singh (2004)

Czechoslovak Mathematical Journal

Similarity:

A $(p, q)$ -sigraph $S$ is an ordered pair $(G, s)$ where $G = (V, E)$ is a $(p, q)$ -graph and $s$ is a function which assigns to each edge of $G$ a positive or a negative sign. Let the sets $E^{+}$ and $E^{-}$ consist of $m$ positive and $n$ negative edges of $G$ , respectively, where $m + n = q$ . Given positive integers $k$ and $d$ , $S$ is said to be $(k, d)$ -graceful if the vertices of $G$ can be labeled with distinct integers from the set ${0, 1, \dots, k + (q - 1) d}$ such that when each edge $u v$ of $G$ is assigned the product of its sign and the absolute difference of the integers assigned to...

Edge-connectivity of strong products of graphs

Bostjan Bresar, Simon Spacapan (2007)

Discussiones Mathematicae Graph Theory

Similarity:

The strong product G₁ ⊠ G₂ of graphs G₁ and G₂ is the graph with V(G₁)×V(G₂) as the vertex set, and two distinct vertices (x₁,x₂) and (y₁,y₂) are adjacent whenever for each i ∈ 1,2 either $x_{i} = y_{i}$ or $x_{i} y_{i} \in E (G_{i})$ . In this note we show that for two connected graphs G₁ and G₂ the edge-connectivity λ (G₁ ⊠ G₂) equals minδ(G₁ ⊠ G₂), λ(G₁)(|V(G₂)| + 2|E(G₂)|), λ(G₂)(|V(G₁)| + 2|E(G₁)|). In addition, we fully describe the structure of possible minimum edge cut sets in strong products of graphs.

Labeling the vertex amalgamation of graphs

Ramon M. Figueroa-Centeno, Rikio Ichishima, Francesc A. Muntaner-Batle (2003)

Discussiones Mathematicae Graph Theory

Similarity:

A graph G of size q is graceful if there exists an injective function f:V(G)→ 0,1,...,q such that each edge uv of G is labeled |f(u)-f(v)| and the resulting edge labels are distinct. Also, a (p,q) graph G with q ≥ p is harmonious if there exists an injective function $f : V (G) \to Z_{q}$ such that each edge uv of G is labeled f(u) + f(v) mod q and the resulting edge labels are distinct, whereas G is felicitous if there exists an injective function $f : V (G) \to Z_{q + 1}$ such that each edge uv of G is labeled f(u) + f(v) mod...

On well-covered graphs of odd girth 7 or greater

Bert Randerath, Preben Dahl Vestergaard (2002)

Discussiones Mathematicae Graph Theory

Similarity:

A maximum independent set of vertices in a graph is a set of pairwise nonadjacent vertices of largest cardinality α. Plummer [14] defined a graph to be well-covered, if every independent set is contained in a maximum independent set of G. One of the most challenging problems in this area, posed in the survey of Plummer [15], is to find a good characterization of well-covered graphs of girth 4. We examine several subclasses of well-covered graphs of girth ≥ 4 with respect to the odd girth...

Join of two graphs admits a nowhere-zero $3$ -flow

Saieed Akbari, Maryam Aliakbarpour, Naryam Ghanbari, Emisa Nategh, Hossein Shahmohamad (2014)

Czechoslovak Mathematical Journal

Similarity:

Let $G$ be a graph, and $λ$ the smallest integer for which $G$ has a nowhere-zero $λ$ -flow, i.e., an integer $λ$ for which $G$ admits a nowhere-zero $λ$ -flow, but it does not admit a $(λ - 1)$ -flow. We denote the minimum flow number of $G$ by $Λ (G)$ . In this paper we show that if $G$ and $H$ are two arbitrary graphs and $G$ has no isolated vertex, then $Λ (G \lor H) \leq 3$ except two cases: (i) One of the graphs $G$ and $H$ is $K_{2}$ and the other is $1$ -regular. (ii) $H = K_{1}$ and $G$ is a graph with at least one isolated vertex or a component whose every...

Domination in partitioned graphs

Zsolt Tuza, Preben Dahl Vestergaard (2002)

Discussiones Mathematicae Graph Theory

Similarity:

Let V₁, V₂ be a partition of the vertex set in a graph G, and let $γ_{i}$ denote the least number of vertices needed in G to dominate $V_{i}$ . We prove that γ₁+γ₂ ≤ [4/5]|V(G)| for any graph without isolated vertices or edges, and that equality occurs precisely if G consists of disjoint 5-paths and edges between their centers. We also give upper and lower bounds on γ₁+γ₂ for graphs with minimum valency δ, and conjecture that γ₁+γ₂ ≤ [4/(δ+3)]|V(G)| for δ ≤ 5. As δ gets large, however, the largest...