The distinguishing number and the distinguishing index of line and graphoidal graph(s)

DOI10.1016/J.AKCEJ.2018.08.006zbMATH Open1473.05259arXiv1708.05822OpenAlexW2962946956WikidataQ129310563 ScholiaQ129310563MaRDI QIDQ5154552FDOQ5154552

Authors: Saeid Alikhani, Samaneh Soltani 

Publication date: 5 October 2021

Published in: AKCE International Journal of Graphs and Combinatorics (Search for Journal in Brave)

Abstract: The distinguishing number (index) $D(G)$ ($D^{\prime }(G)$) of a graph $G$ is the least integer $d$ such that $G$ has an vertex labeling (edge labeling) with $d$ labels that is preserved only by a trivial automorphism. A graphoidal cover of $G$ is a collection $psi$ of (not necessarily open) paths in $G$ such that every path in $psi$ has at least two vertices, every vertex of $G$ is an internal vertex of at most one path in $psi$ and every edge of $G$ is in exactly one path in $psi$. Let $Omega(G,psi)$ denote the intersection graph of $psi$. A graph $H$ is called a graphoidal graph, if there exists a graph $G$ and a graphoidal cover $psi$ of $G$ such that $HcongOmega(G,psi)$. In this paper, we study the distinguishing number and the distinguishing index of the line graph and the graphoidal graph of a simple connected graph $G$.

Full work available at URL: https://arxiv.org/abs/1708.05822

Recommendations

• Distinguishing number and distinguishing index of certain graphs
• Distinguishing numbers and distinguishing indices of oriented graphs
• Distinguishing number and distinguishing index of join of two specific graphs
• The distinguishing number (index) and the domination number of a graph
• The distinguishing number and the distinguishing index of graphs from primary subgraphs
• The distinguishing number and distinguishing index of the lexicographic product of two graphs
• Distinguishing number and distinguishing index of natural and fractional powers of graphs
• Distinguishing number and distinguishing index of strong product of two graphs
• A bound for the distinguishing index of regular graphs
• A note on the line‐distinguishing chromatic number and the chromatic index of a graph

zbMATH Keywords

distinguishing numberdistinguishing indexline and graphoidal graphs

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cites Work

• Graph derivatives
• Symmetry breaking in graphs
• Characterizations of derived graphs
• Graphoidal covers and graphoidal covering number of a graph
• The distinguishing chromatic number
• Distinguishing graphs by edge-colourings
• Graphoidal bipartite graphs
• Improving upper bounds for the distinguishing index

Cited In (5)

• The distinguishing number (index) and the domination number of a graph
• Distinguishing number of hierarchical products of graphs
• Edge-determining sets and determining index
• Asymmetric edge-colorings of graphs with three colors
• The distinguishing number and the distinguishing index of graphs from primary subgraphs

This page was built for publication: The distinguishing number and the distinguishing index of line and graphoidal graph(s)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5154552)