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

DOI10.1016/J.AKCEJ.2018.08.006MaRDI QIDQ5154552zbMATH OpenOpenAlexWikidataFDO

Authors Saeid Alikhani, Samaneh Soltani

Publication date 5 October 2021

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

Copyright license Creative Commons Attribution 4.0 International

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

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)

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

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

Cites work

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

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)