The main vertices of a star set and related graph parameters

DOI10.1016/J.DISC.2021.112593MaRDI QIDQ2231707zbMATH OpenOpenAlexFDO

Authors Milica Andelić, Zoran Stanić, D. M. Cardoso, Slobodan K. Simić

Publication date 30 September 2021

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

isomorphism problemmain eigenvaluemain vertexstar set

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Combinatorial optimization (90C27)

Abstract: A vertex $vinV(G)$ is called $lambda$-main if it belongs to a star set $XsubsetV(G)$ of the eigenvalue $lambda$ of a graph $G$ and this eigenvalue is main for the graph obtained from $G$ by deleting all the vertices in $Xsetminusv$; otherwise, $v$ is $lambda$-non-main. Some results concerning main and non-main vertices of an eigenvalue are deduced. For a main eigenvalue $lambda$ of a graph $G$, we introduce the minimum and maximum number of $lambda$-main vertices in some $lambda$-star set of $G$ as new graph invariant parameters. The determination of these parameters is formulated as a combinatorial optimization problem based on a simplex-like approach. Using these and some related parameters we develop new spectral tools that can be used in the research of the isomorphism problem. Examples of graphs for which the maximum number of $lambda$-main vertices coincides with the cardinality of a $lambda$-star set are provided.

Recommendations

• Vertex-Disjoint Stars in Graphs
• scientific article; zbMATH DE number 1529454
• scientific article; zbMATH DE number 1347012
• Some characterizations of graphs by star complements
• scientific article; zbMATH DE number 1153450
• scientific article; zbMATH DE number 5583535
• On the characterization of graphs by star complements
• On topological properties of the \(n\)-star graph
• On graphs whose star sets are (co-)cliques
• Topological properties of star graphs

Cites work

• A simplex like approach based on star sets for recognizing convex-QP adverse graphs
• An introduction to the theory of graph spectra
• Dominating Sets and Eigenvalues of Graphs
• Eigenspaces of graphs
• scientific article; zbMATH DE number 4070954 (Why is no real title available?)
• scientific article; zbMATH DE number 1234104 (Why is no real title available?)
• scientific article; zbMATH DE number 1503621 (Why is no real title available?)
• scientific article; zbMATH DE number 3324507 (Why is no real title available?)
• New results on the average behavior of simplex algorithms
• On graphs whose second largest eigenvalue equals 1 -- the star complement technique
• On graphs with just three distinct eigenvalues
• Regular graphs. A spectral approach
• Relations between ( , )-regular sets and star complements.
• The main eigenvalues of a graph: a survey

This page was built for publication: The main vertices of a star set and related graph parameters

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