Metric dimension and zero forcing number of two families of line graphs

Linda Eroh; Cong X. Kang; Eunjeong Yi

Displaying similar documents to “Metric dimension and zero forcing number of two families of line graphs”

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

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

Destroying symmetry by orienting edges: complete graphs and complete bigraphs

Frank Harary, Michael S. Jacobson (2001)

Discussiones Mathematicae Graph Theory

Similarity:

Our purpose is to introduce the concept of determining the smallest number of edges of a graph which can be oriented so that the resulting mixed graph has the trivial automorphism group. We find that this number for complete graphs is related to the number of identity oriented trees. For complete bipartite graphs $K_{s, t}$ , s ≤ t, this number does not always exist. We determine for s ≤ 4 the values of t for which this number does exist.

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

Clopen graphs

Stefan Geschke (2013)

Fundamenta Mathematicae

Similarity:

A graph G on a topological space X as its set of vertices is clopen if the edge relation of G is a clopen subset of X² without the diagonal. We study clopen graphs on Polish spaces in terms of their finite induced subgraphs and obtain information about their cochromatic numbers. In this context we investigate modular profinite graphs, a class of graphs obtained from finite graphs by taking inverse limits. This continues the investigation of continuous colorings on Polish spaces and their...

A Finite Characterization and Recognition of Intersection Graphs of Hypergraphs with Rank at Most 3 and Multiplicity at Most 2 in the Class of Threshold Graphs

Yury Metelsky, Kseniya Schemeleva, Frank Werner (2017)

Discussiones Mathematicae Graph Theory

Similarity:

We characterize the class [...] L32 $L_{3}^{2}$ of intersection graphs of hypergraphs with rank at most 3 and multiplicity at most 2 by means of a finite list of forbidden induced subgraphs in the class of threshold graphs. We also give an O(n)-time algorithm for the recognition of graphs from [...] L32 $L_{3}^{2}$ in the class of threshold graphs, where n is the number of vertices of a tested graph.

On Ramsey $(K_{1, 2}, K ₙ)$ -minimal graphs

Mariusz Hałuszczak (2012)

Discussiones Mathematicae Graph Theory

Similarity:

Let F be a graph and let , denote nonempty families of graphs. We write F → (,) if in any 2-coloring of edges of F with red and blue, there is a red subgraph isomorphic to some graph from G or a blue subgraph isomorphic to some graph from H. The graph F without isolated vertices is said to be a (,)-minimal graph if F → (,) and F - e not → (,) for every e ∈ E(F). We present a technique which allows to generate infinite family of (,)-minimal graphs if we know some special graphs. In particular,...

On 2-periodic graphs of a certain graph operator

Ivan Havel, Bohdan Zelinka (2001)

Discussiones Mathematicae Graph Theory

Similarity:

We deal with the graph operator $\bar{P o w ₂}$ defined to be the complement of the square of a graph: $\bar{P o w ₂} (G) = \bar{P o w ₂ (G)}$ . Motivated by one of many open problems formulated in [6] we look for graphs that are 2-periodic with respect to this operator. We describe a class of bipartite graphs possessing the above mentioned property and prove that for any m,n ≥ 6, the complete bipartite graph $K_{m, n}$ can be decomposed in two edge-disjoint factors from . We further show that all the incidence graphs of Desarguesian finite projective...