Displaying similar documents to “Median of a graph with respect to edges”

On signed edge domination numbers of trees

Bohdan Zelinka (2002)

Mathematica Bohemica

Similarity:

The signed edge domination number of a graph is an edge variant of the signed domination number. The closed neighbourhood N G [ e ] of an edge e in a graph G is the set consisting of e and of all edges having a common end vertex with e . Let f be a mapping of the edge set E ( G ) of G into the set { - 1 , 1 } . If ∑ x ∈ N [ e ] f ( x ) ≥ 1 for each e ∈ E ( G ) , then f is called a signed edge dominating function on G . The minimum of the values ∑ x ∈ E ( G ) f ( x ) , taken over all signed edge dominating function f on G , is called the signed edge domination number...

On k-intersection edge colourings

Rahul Muthu, N. Narayanan, C.R. Subramanian (2009)

Discussiones Mathematicae Graph Theory

Similarity:

We propose the following problem. For some k ≥ 1, a graph G is to be properly edge coloured such that any two adjacent vertices share at most k colours. We call this the k-intersection edge colouring. The minimum number of colours sufficient to guarantee such a colouring is the k-intersection chromatic index and is denoted χ’ₖ(G). Let fₖ be defined by f ₖ ( Δ ) = m a x G : Δ ( G ) = Δ χ ' ₖ ( G ) . We show that fₖ(Δ) = Θ(Δ²/k). We also discuss some open problems.

The crossing number of the generalized Petersen graph P [ 3 k , k ]

Stanley Fiorini, John Baptist Gauci (2003)

Mathematica Bohemica

Similarity:

Guy and Harary (1967) have shown that, for k ≥ 3 , the graph P [ 2 k , k ] is homeomorphic to the Möbius ladder M 2 k , so that its crossing number is one; it is well known that P [ 2 k , 2 ] is planar. Exoo, Harary and Kabell (1981) have shown hat the crossing number of P [ 2 k + 1 , 2 ] is three, for k ≥ 2 . Fiorini (1986) and Richter and Salazar (2002) have shown that P [ 9 , 3 ] has crossing number two and that P [ 3 k , 3 ] has crossing number k , provided k ≥ 4 . We extend this result by showing that P [ 3 k , k ] also has crossing number k for all k ≥ 4 .

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 ) → 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 ) → Z q + 1 such that each edge uv of G is labeled f(u) + f(v) mod...

Point-distinguishing chromatic index of the union of paths

Xiang'en Chen (2014)

Czechoslovak Mathematical Journal

Similarity:

Let G be a simple graph. For a general edge coloring of a graph G (i.e., not necessarily a proper edge coloring) and a vertex v of G , denote by S ( v ) the set (not a multiset) of colors used to color the edges incident to v . For a general edge coloring f of a graph G , if S ( u ) ≠ S ( v ) for any two different vertices u and v of G , then we say that f is a point-distinguishing general edge coloring of G . The minimum number of colors required for a point-distinguishing general edge coloring of G , denoted...

The eavesdropping number of a graph

Jeffrey L. Stuart (2009)

Czechoslovak Mathematical Journal

Similarity:

Let G be a connected, undirected graph without loops and without multiple edges. For a pair of distinct vertices u and v , a minimum { u , v } -separating set is a smallest set of edges in G whose removal disconnects u and v . The edge connectivity of G , denoted λ ( G ) , is defined to be the minimum cardinality of a minimum { u , v } -separating set as u and v range over all pairs of distinct vertices in G . We introduce and investigate the eavesdropping number, denoted ε ( G ) , which is defined to be the maximum cardinality...