Some necessary conditions for a graph to be Hamiltonian (Q2482325): Difference between revisions
From MaRDI portal
Created claim: MaRDI profile type (P1460): MaRDI publication profile (Q5976449), #quickstatements; #temporary_batch_1710339121855 |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s00022-007-1953-4 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2015218873 / rank | |||
Normal rank |
Latest revision as of 02:49, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Some necessary conditions for a graph to be Hamiltonian |
scientific article |
Statements
Some necessary conditions for a graph to be Hamiltonian (English)
0 references
16 April 2008
0 references
Let \(G\) be a graph on \(v\) vertices and \(s\) edges, and let \(S= \{a_1,\dots, a_n\}\) be a set of \(n\leq s\) symbols. Associate with each edge \(e\) a symbol of \(S\) such that two edges \(e\), \(f\) are associate with the same symbol only if there is an automorphism of \(G\) mapping \(e\) onto \(f\). For every vertex \(x\) define the spectrum \(S(x)\) to be the \((1\times n)\)-matrix whose \(i\)th entry is the number of edges incident with \(x\) and associated with \(a_i\). Two vertices are equivalent if they have the same spectrum. Let \(V_1,\dots, V_m\) be the equivalence classes, and denote by \(S_1,\dots, S_m\) the corresponding spectra. The spectral matrix \(M\) of \(G\) is the \((m\times n)\)-matrix whose \(i\)th row is \(S_i\); the extended spectral matrix \(M'\) of \(G\) arises by augmenting \(M\) by an \((n+1)\)th column whose entries are all \(1\). The difference spectral matrix \(M''\) is the \(((m- 1)\times n)\)-matrix whose \(j\)th row is \(S_1- S_j\), \(2\leq j\leq m\). The authors prove 1. If \(G\) is Hamiltonian, then \(r(M)= r(M')\). 2. If \(G\) is Hamiltonian, then \(r(M')\leq n\). 3. If \(G\) is Hamiltonian and not all spectra are the same, then \(r(M'')< n\). Thus, if \(m= n+1\) then \(\det M''= 0\). The authors demonstrate these results by looking at various examples as well.
0 references