On k-intersection edge colourings

Rahul Muthu; N. Narayanan; C.R. Subramanian

Displaying similar documents to “On k-intersection edge colourings”

Median of a graph with respect to edges

A.P. Santhakumaran (2012)

Discussiones Mathematicae Graph Theory

Similarity:

For any vertex v and any edge e in a non-trivial connected graph G, the distance sum d(v) of v is $d (v) = \sum_{u \in V} d (v, u)$ , the vertex-to-edge distance sum d₁(v) of v is $d ₁ (v) = \sum_{e \in E} d (v, e)$ , the edge-to-vertex distance sum d₂(e) of e is $d ₂ (e) = \sum_{v \in V} d (e, v)$ and the edge-to-edge distance sum d₃(e) of e is $d ₃ (e) = \sum_{f \in E} d (e, f)$ . The set M(G) of all vertices v for which d(v) is minimum is the median of G; the set M₁(G) of all vertices v for which d₁(v) is minimum is the vertex-to-edge median of G; the set M₂(G) of all edges e for which d₂(e) is minimum is the edge-to-vertex...

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 \geq 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 \geq 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 \geq 4$ . We extend this result by showing that $P [3 k, k]$ also has crossing number $k$ for all $k \geq 4$ .

Maximum Edge-Colorings Of Graphs

Stanislav Jendrol’, Michaela Vrbjarová (2016)

Discussiones Mathematicae Graph Theory

Similarity:

An r-maximum k-edge-coloring of G is a k-edge-coloring of G having a property that for every vertex v of degree dG(v) = d, d ≥ r, the maximum color, that is present at vertex v, occurs at v exactly r times. The r-maximum index [...] χr′(G) $χ_{r}^{'} (G)$ is defined to be the minimum number k of colors needed for an r-maximum k-edge-coloring of graph G. In this paper we show that [...] χr′(G)≤3 $χ_{r}^{'} (G) \leq 3$ for any nontrivial connected graph G and r = 1 or 2. The bound 3 is tight. All graphs G with [...] χ1′(G)=i...

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) \neq 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...

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 $\sum_{x \in N [e]} f (x) \geq 1$ for each $e \in E (G)$ , then $f$ is called a signed edge dominating function on $G$ . The minimum of the values $\sum_{x \in E (G)} f (x)$ , taken over all signed edge dominating function $f$ on $G$ , is called the signed edge domination number...

Localization of jumps of the point-distinguishing chromatic index of $K_{n, n}$

Mirko Horňák, Roman Soták (1997)

Discussiones Mathematicae Graph Theory

Similarity:

The point-distinguishing chromatic index of a graph represents the minimum number of colours in its edge colouring such that each vertex is distinguished by the set of colours of edges incident with it. Asymptotic information on jumps of the point-distinguishing chromatic index of $K_{n, n}$ is found.

Kaleidoscopic Colorings of Graphs

Gary Chartrand, Sean English, Ping Zhang (2017)

Discussiones Mathematicae Graph Theory

Similarity:

For an r-regular graph G, let c : E(G) → [k] = 1, 2, . . . , k, k ≥ 3, be an edge coloring of G, where every vertex of G is incident with at least one edge of each color. For a vertex v of G, the multiset-color cm(v) of v is defined as the ordered k-tuple (a1, a2, . . . , ak) or a1a2 … ak, where ai (1 ≤ i ≤ k) is the number of edges in G colored i that are incident with v. The edge coloring c is called k-kaleidoscopic if cm(u) ≠ cm(v) for every two distinct vertices u and v of G. A regular...

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...