On the Trace Norms of Orientations of Graphs
- PDF / 655,865 Bytes
- 16 Pages / 439.37 x 666.142 pts Page_size
- 63 Downloads / 191 Views
On the Trace Norms of Orientations of Graphs Jianping Li1 · Bo Zhou2 Received: 15 July 2019 / Revised: 4 December 2019 © Malaysian Mathematical Sciences Society and Penerbit Universiti Sains Malaysia 2020
Abstract The trace norm of the digraph is defined as the sum of the singular values of its adjacency matrix. We determine the orientations with, respectively, small and large trace norms among orientations of trees and unicyclic graphs, respectively. Keywords Trace norm · Energy · Digraph · Orientation · Tree · Unicyclic graph Mathematics Subject Classification 05C50 · 05C20 · 15A18
1 Introduction We consider digraphs without loops or multiple arcs. Let D be a digraph with vertex set V (D) and arc set E(D). Denote by uv the arc from vertex u to vertex v (i.e., the arc with tail u and head v). The outdegree (indegree, respectively) of a vertex u of + − (u) (d D (u), respectively), is the number of arcs of the form uv (vu, D, denoted by d D + − (u) + d D (u) = 1 is a leaf of D. A vertex u with respectively) in D. A vertex u with d D + − d D (u) = 0 (d D (u) = 0, respectively) is called a sink (source, respectively) of D. The transpose D of a digraph D is obtained from D by reversing all arcs. The adjacency matrix of an n-vertex digraph D is the n × n matrix A(D) = (auv )u,v∈V (G) , where auv = 1 if uv ∈ E(D) and 0 otherwise. We mention that a (simple undirected) graph G corresponds naturally to a digraph D(G) with the same vertex set such that if there is an edge connecting vertices u
Communicated by Sanming Zhou.
B
Bo Zhou [email protected] Jianping Li [email protected]
1
Faculty of Applied Mathematics, Guangdong University of Technology, Guangzhou 510090, People’s Republic of China
2
School of Mathematical Sciences, South China Normal University, Guangzhou 510631, People’s Republic of China
123
J. Li, B. Zhou Fig. 1 Digraph Yn
Yn
and v in G, then there are arcs uv and vu in D(G). The adjacency matrix of G is A(G) = A(D(G)). An orientation of a graph G is a digraph obtained by choosing a direction for each edge of G. A source-sink orientation (SS-orientation for short) of a graph G is an orientation such that each vertex is either a source or a sink. For a real matrix M, its trace norm N (M) is the sum of singular values of M (i.e., the square roots of the eigenvalues of M M T ). For a (0, 1)-matrix M, bounds on N (M) may be found in [7,12]. Agudelo et al. [3] studied the trace norm of a matrix related to the Laplacian matrix of a digraph. For a digraph D, we call N (A(D)) the trace norm of D. Let σ1 , . . . , σn be the singular values of the A(D), arranged in a non-increasing order, where n = |V (D)|. n σi . If G is a graph, then ε(G) = N (D(G)) is just the energy of Then, N (D) = i=1
G, a graph invariant with many applications, being extensively studied [4,8]. − → Let Pn be a path on n vertices, and denote by Pn the directed path on n vertices. − → The vertices of Pn may be labeled as v1 , . . . , vn such that its arcs are vi vi+1 for − → i = 1, . . . , n − 1. Under this labeling, v1 is the o
Data Loading...
