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

Stanley Fiorini; John Baptist Gauci

Displaying similar documents to “The crossing number of the generalized Petersen graph $P [3 k, k]$ ”

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

New edge neighborhood graphs

Ali A. Ali, Salar Y. Alsardary (1997)

Czechoslovak Mathematical Journal

Similarity:

Let $G$ be an undirected simple connected graph, and $e = u v$ 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 $𝒩_{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 $𝒩_{e}$ . Balasubramanian and Alsardary [1] obtained some other graphs in $𝒩_{e}$ . In this paper we given some new graphs in $𝒩_{e}$ .

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

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

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

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

On local structure of 1-planar graphs of minimum degree 5 and girth 4

Dávid Hudák, Tomás Madaras (2009)

Discussiones Mathematicae Graph Theory

Similarity:

A graph is 1-planar if it can be embedded in the plane so that each edge is crossed by at most one other edge. We prove that each 1-planar graph of minimum degree 5 and girth 4 contains (1) a 5-vertex adjacent to an ≤ 6-vertex, (2) a 4-cycle whose every vertex has degree at most 9, (3) a $K_{1, 4}$ with all vertices having degree at most 11.

Displaying similar documents to “The crossing number of the generalized Petersen graph P [ 3 k , k ] ”

Displaying similar documents to “The crossing number of the generalized Petersen graph $P [3 k, k]$ ”