Here's my summary of the comments/answer I've got so far, combined with my own research.
When requesting for Android, you need to consider two things:
- Different screen sizes
- Different screen resolutions
Let's assume you want to support all possible configurations. You need to provide resources for each screen size below
- Small (approx. 240px x 320px)
- Normal (approx. 320px × 480px)
- Large (approx. 400px x 800px)
- Extra Large (approx. 1024px x 800px)
Android is used on a range of devices, so 'small' and large' are categories, not specific sizes. For each individual device, regardless of screen size, you will also need to consider its resolution -- dots per inch (dpi).
Android devices are categorised as having
- low density (120dpi)
- medium density (160dpi)
- high density (240dpi)
- extra high density (320dpi)
For the 'star' graphic in my wireframe, I need my graphic designer to provide 16 versions of each graphic -- to fit on 4 screen sizes x 4 resolutions.
For some assets, e.g. a background 'wallpaper' image, both portrait and landscape mode versions may be required. So I need to request 32 (16 x 2) versions of the wallpaper image!
One other consideration is states, e.g. buttons. Interactive UI elements will require more than one state (4 states are recommended by Google).
If you don't provide all versions of the graphics, Android will automatically try to create them by scaling up/down from the versions you did supply.
So, what format? Both PNGs and JPGs are fine, but PNGs are preferred.
Android also supports a lesser-known format called 9-patch PNGs -- a useful, if technical, way to create a reusable backgrounds for buttons, etc.
There may be a neat solution in svg-android, which is a technical tool that, if implemented by your developer, uses a single SVG format file (otherwise not supported) and redraws it for all the required screen sizes and resolutions. I haven't tried the svg-android approach. It does seem to have certain limitations and restrictions. But it does seem promising.
In fact, I haven't gone through the process of requesting graphics from a designer and creating an app yet. This answer documents my research. I will update this answer when I have completed the process.
Smashing Magazine - Designing for Android
Android Developer Guide - Supporting Multiple Screens